现在我知道以前有关于这个算法的问题，但是老实说我还没有遇到过简单的 java 实现。许多人在他们的 GitHub 个人资料中复制并粘贴了相同的代码，这让我很恼火。
因此，出于面试练习的目的，我计划使用不同的方法来设置和实施算法。
该算法往往非常非常具有挑战性。老实说，我不知道该怎么做。只是逻辑没有意义。我几乎花了 4 天的时间直接绘制该方法，但无济于事。
因此，请用您的智慧启发我们。
我主要是根据这些信息做算法Intuition behind the Aho-Corasick string matching algorithm
如果可以在这里实现自己的解决方案，那将是一个很大的好处。
但这是我真正陷入困境的以下不完整且不起作用的解决方案：
如果您对代码感到不知所措，那么主要问题在于 Aho-Corasick 的主要算法。我们已经很好地创建了字典树。
但问题是，既然我们有了 trie 结构，我们如何真正开始实施。
这些资源都没有帮助。
public class DeterminingDNAHealth {
private Trie tree;
private String[] dictionary;
private Node FailedNode;
private DeterminingDNAHealth() {
}
private void buildMatchingMachine(String[] dictionary) {
this.tree = new Trie();
this.dictionary = dictionary;
Arrays.stream(dictionary).forEach(tree::insert);
}
private void searchWords(String word, String[] dictionary) {
buildMatchingMachine(dictionary);
HashMap < Character, Node > children = tree.parent.getChildren();
String matchedString = "";
for (int i = 0; i < 3; i++) {
char C = word.charAt(i);
matchedString += C;
matchedChar(C, matchedString);
}
}
private void matchedChar(char C, String matchedString) {
if (tree.parent.getChildren().containsKey(C) && dictionaryContains(matchedString)) {
tree.parent = tree.parent.getChildren().get(C);
} else {
char suffix = matchedString.charAt(matchedString.length() - 2);
if (!tree.parent.getParent().getChildren().containsKey(suffix)) {
tree.parent = tree.parent.getParent();
}
}
}
private boolean dictionaryContains(String word) {
return Arrays.asList(dictionary).contains(word);
}
public static void main(String[] args) {
DeterminingDNAHealth DNA = new DeterminingDNAHealth();
DNA.searchWords("abccab", new String[] {
"a",
"ab",
"bc",
"bca",
"c",
"caa"
});
}
}我已经设置了一个工作正常的 trie 数据结构。所以这里没问题
特里.java
public class Trie {
public Node parent;
public Node fall;
public Trie() {
parent = new Node('⍜');
parent.setParent(new Node());
}
public void insert(String word) {...}
private boolean delete(String word) {...}
public boolean search(String word) {...}
public Node searchNode(String word) {...}
public void printLevelOrderDFS(Node root) {...}
public static void printLevel(Node node, int level) {...}
public static int maxHeight(Node root) {...}
public void printTrie() {...}
}节点也是一样的。
节点.java
public class Node {
private char character;
private Node parent;
private HashMap<Character, Node> children = new HashMap<Character, Node>();
private boolean leaf;
// default case
public Node() {}
// constructor accepting the character
public Node(char character) {
this.character = character;
}
public void setCharacter(char character) {...}
public char getCharacter() {...}
public void setParent(Node parent) {...}
public Node getParent() {...}
public HashMap<Character, Node> getChildren() {...}
public void setChildren(HashMap<Character, Node> children) {...}
public void resetChildren() {...}
public boolean isLeaf() {...}
public void setLeaf(boolean leaf) {...}
}