Longest repeated substring problem とは

コンピュータサイエンスでは、最も長いサブストリングの繰り返し問題は、少なくとも2回発生するストリングの最長部分文字列を見つける問題です。
この問題は、文字列のサフィックスツリー( '$'のような特別な文字列の終わりの記号を付加したもの)を構築し、ツリー内の最も深い内部ノードを見つけることで、線形時間と空間 Θ ( n ) {\displaystyle \Theta (n)} で解くことができます。深さは、ルートからトラバースされた文字数で測定されます。ルートからそのようなノードへの綴りの文字列は、最も長い繰り返し部分文字列です。少なくとも k {\displaystyle k} 個のオカレンスを持つ最長部分文字列を見つける問題は、最初にツリーを前処理して、各内部ノードのリーフ子孫の数を数え、次に少なくとも k {\displaystyle k} リーフ子孫を持つ最も深いノードを見つけることで解決できます子供はいない。繰り返しの重複を避けるために、接尾辞の長さのリストに、接頭辞の長さの差より小さい連続する要素がないことを確認できます。
文字列 "ATCGATCGA $"を含む図では、少なくとも2回繰り返す最長の部分文字列は "ATCGA"です。