最長繰り返し部分文字列問題

コンピュータ サイエンスにおいて、最長繰り返し部分文字列問題とは、少なくとも 2 回出現する 文字列の最長部分文字列を見つける問題です。

この問題は、文字列の接尾辞ツリーを構築し('$' などの特殊な文字列終了記号を付加)、ツリー内で複数の子を持つ最も深い内部ノードを見つけることで、線形時間と空間で解決できます。深さは、ルートからトラバースされた文字数で測定されます。ルートからそのようなノードまでのエッジによって綴られる文字列は、最長の繰り返し部分文字列です。少なくとも 回の出現を持つ最長の部分文字列を見つける問題は、最初にツリーを前処理して各内部ノードの葉の子孫の数を数え、次に少なくとも 回の葉の子孫を持つ最も深いノードを見つけることで解決できます。重複した繰り返しを回避するには、接尾辞の長さのリストに、プレフィックス長の差よりも小さい連続した要素がないことを確認します。 ${\displaystyle \Theta (n)}$${\displaystyle k}$${\displaystyle k}$

文字列「ATCGATCGA$」の図では、少なくとも 2 回繰り返される最長の部分文字列は「ATCGA」です。

• Allison, L.「Suffix Trees」。2008年10月14日閲覧。
• サフィックスツリーを使用した最長繰り返し部分文字列の C 実装
• オンラインデモ: 最長繰り返し部分文字列