複数の文字列間で最も長い共通部分文字列を見つけるプログラムに取り組んでいます。接尾辞配列または接尾辞ツリーのいずれかを使用するようにアプローチを下げました。どちらがより良いアプローチであるか (もしあれば) とその理由を知りたいです。また、サフィックス配列については、2 つの文字列のアルゴリズムをいくつか見ましたが、2 つ以上の文字列のアルゴリズムは見ませんでした。堅実な例をいただければ幸いです。アドバイスをありがとうございます。
注: この問題に具体的に対処する他の質問はありませんでしたが、存在する場合はその方向を教えてください!
すべてのシーケンスで発生する部分文字列がある場合、接尾辞配列では、その部分文字列の各発生へのポインターは近くにソートする必要があります。したがって、サフィックス配列に沿ってウィンドウを移動することで、それらを見つけようとすることができます。ウィンドウは、各シーケンスの少なくとも 1 つの出現を含むのに十分な大きさです。各シーケンスについて、そのウィンドウ内でそのシーケンスが何回発生するかを示すテーブルを維持することにより、線形時間でこれを行うことができます。次に、ウィンドウの後端を前方に移動すると、スキップしたばかりのポインターに関連付けられているシーケンスのカウントが減少し、必要に応じて、ウィンドウの前端を移動して、このシーケンスの新しい発生を取得するのに十分なだけになります。そしてテーブルを更新します。
ここで、ウィンドウ内のポインターから始まるすべての部分文字列によって共有される共通のプレフィックスの長さを見つけることができる必要があります。これは、ウィンドウ内のポインター間で発生する最小 LCP 値である必要があります。Java Treeset などの赤黒ツリーを使用し、LCP 値を最も重要なコンポーネントとして構成し、ポインター自体などのタイブレーカーを重要度の低いコンポーネントとして構成するキーを使用する場合、最小値を維持できます。ウィンドウ内の LCP 値は、ウィンドウ調整ごとに大まかにログ ウィンドウ サイズを犠牲にします。