c - 文字列自体の最長共通部分文字列

Question

のような文字列が与えられた場合、文字"geekthegeertheregeers"列自体で最も長い共通部分文字列を見つける必要があります。

この場合の"geer"ように、最長の共通部分文字列になります。私の質問は、ここでどのアルゴリズムが適用されるかということです。この問題のこの解決策を見つけるために LCS を変更できますか?

Answer 1

「部分文字列セットで複数回出現する最長の部分文字列を見つける」という質問ですか? 「geekthegeertheregeers」の結果は「egeer」になるはずですか?

その場合、入力文字列の接尾辞配列を構築し、接尾辞配列の LCP (Longest Common Prefix) 配列を構築できます。どちらも O(N) (N は入力文字列の長さ) で実行できます。

参照：

1. サフィックス配列 ( http://en.wikipedia.org/wiki/Suffix_array )
2. LCP 配列 ( http://en.wikipedia.org/wiki/LCP_array )