8

一致する文字列とパターンが与えられた場合、0または1つの不一致がある一致をどれだけ効率的に見つけることができますか。

e.g) 
S = abbbaaabbbabab
P = abab

Matches are abbb(index 0),aaab(index 4),abbb(index 6),abab(index 10)

KMPアルゴリズムを変更しようとしましたが、アプローチがわかりません。

問題を進めるためのアイデアを教えてください。

ありがとう。

4

4 に答える 4

5

わかりました、見つけました！最高のアルゴリズムを見つけました！

これは少し勇敢に聞こえるかもしれませんが、私が提案するアルゴリズムが実行時間O(m + n)とメモリ消費の両方をO(m + n)持ち、エントリデータ自体が同じプロパティを持っている限り、アルゴリズムは一定でのみ最適化できます。

使用されるアルゴリズム

私のソリューションでは、 KMPアルゴリズムとRabinKarpアルゴリズムを混同して使用します。Rabin Karpは、最初の文字列のサブ文字列を比較するためにローリングハッシュを使用します。線形の追加メモリを使用する線形の時間事前計算が必要ですが、それ以降、2つの文字列のサブ文字列間の比較は一定ですO(1)（これは、衝突を適切に処理すると償却されます）。

私の解決策では何ができないか

私のソリューションでは、最初の文字列で2番目の文字列に一致するすべてのオカレンスを見つけることはできませんが、最大で1つの違いがあります。ただし、アルゴリズムを変更して、最初の文字列のすべての開始インデックスについて、そのような一致がある場合、少なくとも1つが見つかるようにすることができます（これはリーダーに任されています）。

観察

m2番目の文字列の長さと-n最初の文字列の長さとします。タスクを2つの部分に分割します。最大で1つの違いがある一致を見つけることを目的としている場合、最初の文字列の部分文字列を見つけたいと思います。PREF単一の違いの前のSUFF部分文字列と後の部分文字列になります。違い。必要に応じlen(PREF) + len(SUFF) + 1 = mて、PREFまたはSUFF人為的に短縮する必要があります（文字列が違いなく一致する場合）。

私の解決策は、1つの非常に重要な観察に基づいています。最初の文字列のサブ文字列が、最大で1つの違いがある2番目の文字列と一致するi長さのインデックスで始まると仮定します。m次に、PREF可能な限り時間がかかる場合でも、の解決策がありSUFFます。これは明らかです。私は違いを可能な限り最後まで押し進めています。

アルゴリズム

そして今、アルゴリズム自体に従います。通常のKMPから始めます。プレフィックスの拡張が失敗し、失敗したリンクをたどるたびに、最初に次の文字をスキップした場合に残りのサフィックスが2番目の文字列の残りと一致するかどうかを確認します。もしそうなら、最大で1つの文字の違いを持つ求められた一致が見つかります。そうでない場合は、通常のKMPを使用して、フェイルリンクをたどるたびにラビンカープ文字をチェックします。

例を挙げて、ラビン・カープ文字のチェックをさらに明確にしましょう。KMPの特定のステップにあり、2番目の文字列first.substring[i, i + k - 1]の最初の文字と一致することがわかったとしkます。また、文字first[i + k]がとは異なるとしsecond[k]ます。次に、 RabinKarpを使用してfirst.substring[i + k + 1, i + m - 1]正確に一致するかどうかを確認しますsecond.substring[k + 1, m - 1]。これは、開始プレフィックスフォームインデックスiを可能な限り拡張し、最大で1つの違いがある一致があるかどうかを試してみる場合とまったく同じです。

Rabin Karpは、フェイルリンクがたどられた場合にのみ使用されます。これにより、プレフィックスの開始インデックスが少なくとも1つ移動します。つまり、最大でO(n)Rabin Karp呼び出しが使用され、すべてが複雑O(1)で、全体として線形の複雑さがあります。

于 2012-04-15T06:45:34.743 に答える
2

これは、近似文字列マッチング問題として知られています。特定のケースでは、最大編集距離を1にする必要があります。

bitapアルゴリズムは、それを解決するためのかなり高速な方法です。

于 2012-04-12T10:05:40.283 に答える
2

1つの不一致を含むすべてのサブ一致を見つけるには、2つのz関数が必要です（1つは元のP用、もう1つは逆P用）。その後、元の文字列と反転された文字列Sの最長のプレフィックスサブマッチのbuld配列。後で、2番目の配列を反転する必要があります。そして、最終的にはすべてが簡単です。最初の配列を調べて、最長のプレフィックスの長さがPの長さと等しいかどうかを確認します。等しい場合は、間違いなく一致します。短い場合は、位置（i + length（P）-1）の2番目の配列を確認します。2つの値の合計がlength（P）-1に等しい場合、それは1つの間違いを伴う部分一致です。

複雑さはO（len（P）+ len（S））です

于 2012-06-02T09:44:08.160 に答える
1

さまざまなアルゴリズムの包括的な概要と、それらが互いにどのように比較されるかについては、ゴンサロナバロが、文字列マッチングを概算するためのガイド付きツアーで説明しています。ページ80、81、および82は、最悪の場合と平均的な場合、およびさまざまなアルゴリズムのスペース要件を含む、複雑さの結果を示しています。

（ここで使用されている表記法では、nは検索するテキストの長さ、mはパターンの長さ、σはアルファベットのサイズ、kは最大編集距離（この場合は1）を表します。）

于 2012-04-13T01:48:39.400 に答える