接尾辞ツリー（バイナリ文字列）：最も長い部分文字列を見つけよう

Question

補完的な文字列（ビット単位）を持つ文字列の中で最も長い部分文字列を見つける効率的なアルゴリズムを探しています。

私は補完的な文字列のビット単位を言って何を意味すること：

100011 
011100 

Answer 1

サフィックスツリー構築に依存する単純なO（n）アルゴリズムを次に示します。

元の文字列sと補完文字列s 'を同じ接尾辞ツリー（O（n）時間）に読み込みます。そして、f（x）（f '（x））に接尾辞s（resp。）が含まれている場合、真になる各ノードxの2つのフラグf（x）とf' s '）。今度は、単にツリーをたどって、フラグがセットされている最も深いノードを探して、sで補数も同じsで最長の文字列を見つけました。後処理はまた、O（n）時間にしか費用がかからず、従って、総稼働時間はO（n）である。

Answer 2

次のアルゴリズムは、最悪の場合O(n * n)と平均的なケースだけビット超線形です。長い共通部分文字列がたくさんあるときは、最悪の場合に当てはまります。

文字列の任意の点から始めることによって形成できる部分文字列のセットを考えてみましょう。可能な一致が1つしかない場合、元の文字列内の位置へのポインタで終わる部分文字列のトライを作成します。 n個の部分文字列のそれぞれについてこのトライを処理する必要がありますが、文字列が他の部分文字列と同じ長さの共通部分文字列をたどるだけで済みます。

このデータ構造を作成したら、部分文字列をその補数とペアにするために、トライを再帰的に実行します。トライの構造は、ペアリングを非常に効率的にする必要があります。なぜなら、反対側の部分文字列をペアリングするだけで、文字列内の他の場所のすべてを含む部分文字列ではないからです。

補数が一般的ではない文字が一般的な場合は、遅延を遅らせることでパフォーマンスを向上させることができます。