Проблемы оптимизации с Aho Corasick (Java 8)

Question

Я пробовал эту задачу в HackerRank в течение нескольких дней и до сих пор не смог найти решение, которое прошло бы все тестовые случаи, все из-за таймаутов:

https://www.hackerrank.com/challenges/determining-dna-health/problem

Я пытался реализовать Aho-Corasick для этой конкретной проблемы c, и очень хочу играть честно и учиться, но мне нужна помощь, может быть, если вы, ребята, можете проверить мой код и дать некоторые предложения ( включая избавление от всего этого и начало заново), это было бы здорово.

Извините за мою плохую грамматику, Engli sh не мой родной язык.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.stream.Stream;


public class Driver {
    static String[] words;
    static int[] scores; 
    static ACFinder finder = new ACFinder();
    public static void main(String... args) {
        try(BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            reader.readLine();
            words = reader.readLine().split(" ");
            scores = Stream.of(reader.readLine().split(" ")).mapToInt(e -> Integer.parseInt(e)).toArray();
            int numberOfTests = Integer.parseInt(reader.readLine());
            long minScore = Long.MAX_VALUE;
            long maxScore = Long.MIN_VALUE;
            //Building the Trie
            for(int j = 0; j < words.length; j++) {
                finder.addWord(words[j]);
            }
            for(int i = 0; i < numberOfTests; i++) {
                String problemString = reader.readLine();
                int[] bounds = Stream.of(problemString.split(" ")).limit(2).mapToInt(s -> Integer.parseInt(s)).toArray();
                String toTest = problemString.split(" ")[2];
                long score = drive(bounds, toTest);
                System.out.println(i + "/" + numberOfTests);
                if(score > maxScore)
                    maxScore = score;
                if(score < minScore)
                    minScore = score;
            }
            System.out.println(minScore + " " + maxScore);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    private static long drive(int[] bounds, String toTest) {
        HashMap<String, Long> result = finder.getTest(toTest);
        long score = 0;
        for(int i = bounds[0]; i <= bounds[1]; i++) {
            score += result.get(words[i]) * scores[i];
        }
        return score;
    } 
    private static class ACFinder {
        private HashMap<Character, Edge> rootNode;
        private HashMap<String, Long> answer;
        public ACFinder() {
            rootNode = new HashMap<>();
            answer = new HashMap<>();
        }
        // Return Key: Ocurrencies Valor: Qty Ocurrencies
        public HashMap<String, Long> getTest(String toTest) {
            int length = toTest.length();
            answer.forEach((String j, Long k) -> answer.replace(j, 0L));
            HashMap<Character, Edge> nextNode = rootNode;
            for(int i = 0; i < length; i++) {
                String findingWord = "";
                int lastIndex = i;
                while(nextNode.containsKey(toTest.charAt(i))) {
                    findingWord = findingWord + toTest.charAt(i);;
                    if(nextNode.get(toTest.charAt(i)).isLeaf()) {
                        answer.replace(findingWord, answer.get(findingWord) + 1);
                    } 
                    nextNode = nextNode.get(toTest.charAt(i)).getChildren();
                    if(i < length - 1)
                        i++;
                }
                i = lastIndex;
                nextNode = rootNode;
            }       
            return answer;
        }
        public void addWord(String word) {
            if(!answer.containsKey(word)) {
            answer.put(word, 0L);
            int length = word.length();
            Edge nextNode = null;
            while(word.length() != 0) {
                char nextChar = word.charAt(0);
                if(word.length() == length) {
                    if(rootNode.containsKey(nextChar)) {
                        nextNode = rootNode.get(nextChar);
                    } else {
                        rootNode.put(word.charAt(0), new Edge());
                        nextNode = rootNode.get(nextChar);
                    }
                } else {
                    if(nextNode.getChildren().containsKey(nextChar)) {
                        nextNode = nextNode.getChildren().get(nextChar);
                    } else {
                        nextNode.getChildren().put(word.charAt(0), new Edge());
                        nextNode = nextNode.getChildren().get(nextChar);
                    }
                }
                if(word.length() == 1) {
                    nextNode.setLeaf(true);
                }
                word = word.substring(1);
            }
            }
        }
        private class Edge {
            private HashMap<Character, Edge> children = new HashMap<>();
            private boolean isLeaf;
            private HashMap<Character, Edge> getChildren() {
                return children;
            } 
            private void setLeaf(Boolean leaf) {
                this.isLeaf = leaf;
            }
            private boolean isLeaf() {
                return isLeaf;
            }
        }
    }
}

Редактировать:

Я просто понимаю, насколько неопределенным является этот вопрос, это мой первый вопрос, и, возможно, он может быть более конкретным c в терминах Aho-Corasick:

• Учитывая словарь, некоторые тесты падежи и две границы в этом словаре для поиска совпадений (и их подсчета). Должен ли я построить Tr ie для каждого теста с заданным подмножеством словаря, или использовать один и тот же Tr ie (как в приведенной выше реализации) для каждого теста, даже если мы проверяем не очень ценную информацию?
• Я скачал оригинальную статью для реализации этого алгоритма, но я не уверен, что моя реализация получит все это. Конечно, лучше использовать наивный подход, но, возможно, моя проблема не в оптимизации, а в недостатках реализации:

    public class ACFinder {
        private HashMap<Character, Edge> rootNode;
        private HashMap<String, Long> answer;
        public ACFinder() {
            rootNode = new HashMap<>();
            answer = new HashMap<>();
        }
        // Return Key: Ocurrencies Valor: Qty Ocurrencies
        public HashMap<String, Long> getTest(String toTest) {
            int length = toTest.length();
            answer.forEach((String j, Long k) -> answer.replace(j, 0L));
            HashMap<Character, Edge> nextNode = rootNode;
            for(int i = 0; i < length; i++) {
                String findingWord = "";
                int lastIndex = i;
                while(nextNode.containsKey(toTest.charAt(i))) {
                    findingWord = findingWord + toTest.charAt(i);;
                    if(nextNode.get(toTest.charAt(i)).isLeaf()) {
                        answer.replace(findingWord, answer.get(findingWord) + 1);
                    } 
                    nextNode = nextNode.get(toTest.charAt(i)).getChildren();
                    if(i < length - 1)
                        i++;
                }
                i = lastIndex;
                nextNode = rootNode;
            }       
            return answer;
        }
        public void addWord(String word) {
            if(!answer.containsKey(word)) {
            answer.put(word, 0L);
            int length = word.length();
            Edge nextNode = null;
            while(word.length() != 0) {
                char nextChar = word.charAt(0);
                if(word.length() == length) {
                    if(rootNode.containsKey(nextChar)) {
                        nextNode = rootNode.get(nextChar);
                    } else {
                        rootNode.put(word.charAt(0), new Edge());
                        nextNode = rootNode.get(nextChar);
                    }
                } else {
                    if(nextNode.getChildren().containsKey(nextChar)) {
                        nextNode = nextNode.getChildren().get(nextChar);
                    } else {
                        nextNode.getChildren().put(word.charAt(0), new Edge());
                        nextNode = nextNode.getChildren().get(nextChar);
                    }
                }
                if(word.length() == 1) {
                    nextNode.setLeaf(true);
                }
                word = word.substring(1);
            }
            }
        }
        private class Edge {
            private HashMap<Character, Edge> children = new HashMap<>();
            private boolean isLeaf;
            private HashMap<Character, Edge> getChildren() {
                return children;
            } 
            private void setLeaf(Boolean leaf) {
                this.isLeaf = leaf;
            }
            private boolean isLeaf() {
                return isLeaf;
            }
        }
    }