Z アルゴリズムを使用して、指定された文字列から出現するすべての単語を削除します

この記事では、興味深い文字列操作の問題、「Z アルゴリズムを使用して、指定された文字列から出現するすべての単語を削除する」について詳しく説明します。この問題は、パターン探索問題における Z アルゴリズムの優れた適用例であり、その有効性が強調されています。これについて詳しく見てみましょう。

＃＃＃問題文＃＃＃

文字列 S と単語 W が与えられた場合、タスクは Z アルゴリズムを使用して S から W が出現するすべてを削除することです。

質問を理解する

文字列 S = "HelloWorldHelloWorld" と単語 W = "World" について考えてみましょう。目標は、S から W をすべて削除することです。したがって、出力は「HelloHello」になります。

Z アルゴリズム

Z アルゴリズムは、テキスト内のパターンのすべての出現を線形時間で検索できます。これは、指定されたインデックス i に対して、Z[i] が i から始まる最長の部分文字列の長さを表す配列 (Z 配列) を構築します。これは文字列のプレフィックスでもあります。

アルゴリズム手法

問題を解決する手順は次のとおりです -

新しい文字列 P = W '$' S を作成します。
Z アルゴリズムを P に適用し、Z 配列を構築します。
Z 配列を反復処理します。 Z[i] が W の長さと等しい場合、W がそのインデックスに存在することを意味します。そのインデックスの S から W を削除します。
Example

の中国語訳は次のとおりです:

Example

これは、上記のメソッドを実装する C コードです:

リーリー ＃＃＃出力＃＃＃ リーリー

テストケースの例

例を考えてみましょう -

S = "Iamwritingwriting"、W = "writing" と仮定します。プログラムは「Iam」を出力します。理由は次のとおりです。-

• 新しい文字列 P は「writing$Iamwritingwriting」になります。

• Z アルゴリズムを適用した後、Z[8] と Z[15] が W の長さに等しいことがわかります。これは、W が S のこれらのインデックスに存在することを意味します。

• 次に、これらのインデックスの W を S から削除し、文字列「Iam」を取得します。

  李>
• ＃＃＃結論は＃＃＃

  Z アルゴリズムは、パターン検索の問題を解決するための強力なツールです。この記事では、文字列から出現するすべての単語を削除するという応用例を見ていきました。この質問は、文字列一致アルゴリズムを理解して適用することの利点を示す好例です。アルゴリズムを理解して学習することで、複雑な問題を解決する方法が開かれることを常に覚えておいてください。

以上がZ アルゴリズムを使用して、指定された文字列から出現するすべての単語を削除しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。