圧縮されていないサフィックス ツリーを実装しました。文字列内で最も長く繰り返される部分文字列を見つける問題を解決する方法を知りたかったのです。2 つの子を持つ最も深い内部ノードを見つけなければならないことはわかっていますが、これをどのようにコーディングすればよいでしょうか。また、最も長く繰り返される部分文字列が何であるかを知るにはどうすればよいでしょうか。JAVAのコードに興味があります。PlsはJavaの実装を提供します。参考までに、私のTrieNodeは次のようになります
class TrieNode{
char ch;
LinkedList<TrieNode> child;
}
Aho-Corasick のアルゴリズムhttp://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm
文字列バイトの終わりを格納する場合、2 つの子を持つ最も深いノードのみです。
最長の部分文字列を見つけるには、深さ優先検索を実行し、2 つ以上の子を持つ最も深いノードとその深さへの参照を保持する必要があります。これは、再帰関数で行うのが最も簡単です。
最も深いノードを見つけるには、BFS を実行して最大レベルのノードを選択することもできます。最大レベルのノードも最も深いノードだと思います。次に、2つの子があるかどうかを確認できます。それ以外の場合は高くなります。ただし、これが機能するかどうかはわかりません。コメントはありますか？