-1
今私は、このアルゴリズムに関する以前の質問があることを知っていますが、正直なところ、単純なJavaの実装に遭遇していません。多くの人がGitHubのプロファイルに同じコードをコピーして貼り付けています。Aho-Corasick文字列照合アルゴリズムのJava実装？
インタビューの目的で、別のアプローチを使ってアルゴリズムを設定して実装する予定です。
アルゴリズムは非常に困難な傾向があります。私は正直言って、それについてどうやって行くのか分からない。論理は意味をなさない。私は4日間近く、アプローチをスケッチしていたが、役に立たなかった。
あなたの知恵で教えてください。
私は主に1がここで自分のソリューションを実装することができればそれはビッグボーナスになり、この情報Intuition behind the Aho-Corasick string matching algorithm
に基づくアルゴリズムをやっています。場合は、コードでoverwhelemed、主な問題はアホ - Corasickの主なアルゴリズムであるあなたの
：
しかし、ここでは、私は本当にに引っかかって、次の不完全と動作していないソリューションです。すでに辞書のトライツリーを作成しています。
しかし、私たちはトライストラクチャーを持っているので、実際にどのように実装を開始するのかという問題です。
いずれも参考にしていませんでした。
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() {...}
}ノードの同じこと。
Node.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) {...}
}
* "正直なところ、**単純な** Java実装" * --- * "アルゴリズムは非常に難しい**傾向があります。" * ---おそらくそれが理由です。 – Andreas
したがって、私は大多数が理解できるように、より簡単なアプローチを実装するためにあなたの助けを欲しがっていますよね？ @Andreas – OOP
*「論理は意味をなさない」* ---アルゴリズムを理解できない場合は、コード化する方法がありません。 – Andreas