私はインターネット上で検索しました: k 反復部分文字列の多くのソリューションを、サフィックス ツリーを使用して見つけましたが、サフィックス配列を使用していませんでした。
与えられた文字列: abaababb
繰り返される部分文字列の最大数 ,k = 文字列の長さ = 6
最初は a[0..k]={0}
サブストリングの頻度: "a"= 4 したがって、a[4]=1;
部分文字列の頻度: "ab"= 3 したがって、a[3]=1;
サブストリングの頻度: "b"= 4 したがって、a[4]= a[4]+1 = 2; 等々..
複雑さ: < 配列生成の O(nlogn)。
接尾辞配列の使用:
「abaababb」の接尾辞:
LCP INDEX
0 2 aababb
1 0 abaababb
3 3 ababb
2 5 abb
0 7 b
1 1 baababb
2 4 babb
1 6 bb