接尾辞ツリー：最長の繰り返しサブストリングの実装

Question

圧縮されていない接尾辞ツリーを実装しました。私は、文字列内の最長の再現サブストリングを見つける問題を解決する方法を知りたかったのです。私たちは2人の子供を持つ最も深い内部ノードを見つけなければならないことを知っていますが、これをどのようにコーディングすることができますか。また、最長の繰り返しサブストリングが何であるかをどのように知ることができますか。 Javaのコードに興味があります。 plsはJavaの実装を提供します。参照のために、私の三線は次のように見えます

class TrieNode{

char ch;
LinkedList<TrieNode> child;

}

Answer 1

文字列バイトの端を保存する場合、2人の子供を持つ最も深いノードのみです。

最も長いサブストリングを見つけるには、 深さの最初の検索, 、2人以上の子供を持つ最も深いノードへの参照を保持し、その深さです。これは、再帰機能で最も簡単です。

Answer 2

Aho-Corasickのアルゴリズム http://en.wikipedia.org/wiki/aho%e2%80%93corasick_string_matching_algorithm

Answer 3

最も深いノードを見つけるために、BFSを実行して、最大レベルのノードを選択することもできます。最大レベルのノードも最も深いノードであると思います。その後、2人の子供がいるかどうかを確認できます。それ以外の場合は高くなります。しかし、これが機能するかどうかはわかりません。コメントPPSはありますか？