text - 可能な限り長い繰り返し文字列を見つけるユーティリティ

Question

大きなテキストファイルで最も長く繰り返される部分文字列を見つけて、それらのパターンと各パターンの発生回数を出力できるツール、ユーティリティ、または perl/python スクリプトはありますか?

Answer 1

http://en.wikipedia.org/wiki/Longest_repeated_substring_problem :

最長反復部分文字列の問題は、少なくとも 2 回出現する文字列の最長部分文字列を見つけることです。この問題は、文字列のサフィックス ツリーを構築し、ツリー内の最も深い内部ノードを見つけることにより、線形の時間と空間で解決できます。

• Python のサフィックス ツリー (少し古いですが..): http://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/

• Javascript の実装と詳細な説明: http://www.allisons.org/ll/AlgDS/Tree/Suffix/