繰り返し現れる部分文字列の発見 #2

多分、Suffix Treeを作って、一番深い分岐を調べるという方針になるのかと思います。
Suffix Treeだと大きな文書だとSuffix Arrayを作って順次隣接する要素を比較していけばよいのかと。
どちらの方が速いのかというと、どうなんでしょう？

より正確には Generalized Suffix Tree でしょうか。しかし、Suffix Tree のほうはまったくといっていいほど知らないのだけど、一番深い分岐を探す、ってのがいうほど簡単ではないような。どうなんだろう。
ちなみに自分の回答としては Suffix Array を使う方。Suffix Array 上で隣り合う Suffix 間の共通 prefix の長さは LCP(Longest Common Prefix) と呼ばれるんだけどのこれが一番大きい接尾辞を探せば良い。で、実は Suffix Array 上のすべての suffix に対する LCP を線形時間で計算するアルゴリズムがあるので、それを使えば速いかなぁ、と。