2 つの文字列aとbそれぞれがあります。の長さaは以上ですb。最長の共通部分文字列を見つける必要があります。複数の回答がある場合は、先に来る部分文字列を出力する必要がありますb(開始インデックスが最初に来るように)。
注: と の長さはa最大b10 6です。
サフィックス配列を使用して最長の共通部分文字列を見つけようとしました（クイックソートを使用してサフィックスをソートします）。複数の答えがある場合、最長の共通部分文字列の長さに等しいすべての共通部分文字列をスタックにプッシュしようとしました。
知りたかったのですが、これを行うより速い方法はありますか？
stringの接尾辞ツリーを構築しますa$b。つまり、両方の文字列に存在しないaような文字を連結してから、 と連結します。(圧縮された) サフィックス ツリーは、O(|a|+|b|) 時間とメモリで構築でき、O(|a|+|b|) ノードを持つことができます。$b
これで、各ノードの深さ (ルートから開始し、ツリーをそのノードまでたどることによって得られる文字列の長さ) がわかります。また、2 つのブール量を追跡することもできます。このノードが に対応するビルド フェーズ中にaアクセスされたかどうか、および に対応するビルド フェーズ中にアクセスされたかどうかbです (たとえば、2 つのツリーを別々に構築してからそれらをマージすることもできます)。事前注文トラバーサルを使用します)。ここで、タスクは要約すると、両方のフェーズでアクセスされた最も深い頂点を見つけることになります。これは、1 回の事前注文トラバーサルで実行できます。複数回答の場合は扱いやすいはずです。
このウィキペディアのページには、この手法の別の (簡単な) 概要が含まれています。
これは最長の部分文字列です。探しているのは、繰り返しの有無です。これを読んでください。役立つかもしれません。 http://www.programcreek.com/2013/02/leetcode-longest-substring-without-repeating-characters-java/