序文

コンセプトの紹介

• 文字列：0文字以上の有限のシーケンス
• 空の文字列：0文字の文字列
• スペース文字列：スペースのみを含む文字列
• 空文字列とスペース文字列の違い
  • 空白文字列は長さを持ち、複数の空白を持つことができます。
  • 空文字列は長さを持ちません。
• Substring (部分文字列): 部分文字列を形成する、文字列内の連続した文字の数。
• メイン文字列：部分文字列を含む文字列
• メイン文字列内の部分文字列の位置：メイン文字列内の部分文字列の最初の文字の通し番号
• 文字列記憶構造
  • 逐次記憶構造
  • 連鎖ストレージ構造
• BFアルゴリズム：Brute-Forceアルゴリズムは、シンプルで平易なパターンマッチングアルゴリズムであり、主文字列S内の部分文字列Tの出現を見つけるために一般的に使用されます。

原則

メイン文字列 "toneornot "とパターン文字列 "no "を例に、プレーンパターンマッチングアルゴリズムの実装原理を説明します。

1. 何もしない場合の効果は以下の通りです。

   

2. メイン文字列 "toneornot "の最初の "t "を取り出し、パターン文字列の最初の "n "と比較します。

   

3. メイン文字列 "toneornot "の2番目の "o "を取り出し、パターン文字列の最初の "n "と比較します。

   

4. メイン文字列 "toneornot "の3番目の "n "を取り出し、パターン文字列の最初の "n "と比較します。

   

5. メイン文字列 "toneornot "の4桁目 "e "と、パターン文字列の2桁目 "o "を比較し、等しくない場合は、以下のようになります。

   

6. メイン文字列 "toneornot "の4桁目 "e "を取り出し、パターン文字列の1桁目 "n "と比較します。

   

7. メイン文字列 "toneornot "の5番目の "o "を取り出し、パターン文字列の最初の "n "と比較します。

   

8. メイン文字列 "toneornot "の第6ビット "r "を取り出し、パターン文字列の第1ビット "n "と比較します。

   

9. メイン文字列 "toneornot "の7番目の "n "を取り出し、パターン文字列の最初の "n "と比較します。

   

10. 主音列 "toneornot "の8番目の "o "を取り出し、パターン文字列の2番目の "o "と比較します。この時点で、主音列の中のパターン文字列を見つけることに成功しました。

    

11. メイン文字列 "toneornot "の8番目の "o "を取り出し、パターン文字列の最初の "n "と比較します。

    

12. メイン文字列 "toneornot "の9番目の "t "を、パターン文字列の最初の "n "と比較します。

    

13. パターン "no "は、主音列 "toneornot "の7番目の位置で首尾よく見つかりました。

時間の複雑さ

• プレーンパターンマッチングアルゴリズムの最良の場合の時間複雑度はO(1)です。
• プレーンパターンマッチングアルゴリズムの平均所要時間はO(N+M)。ここでNは主文字列の長さ、Mは部分文字列の長さです。
• プレーンパターンマッチングアルゴリズムの最悪の場合の時間複雑度はO(*M)です。ここでNは主文字列の長さ、Mは部分文字列の長さです。

空間の複雑さ

• プレーンパターンマッチングアルゴリズムの平均空間複雑度はO(N+M)。ここでNは主文字列の長さ、Mは部分文字列の長さです。

アルゴリズムの利点と欠点

• 長所
  • シンプルでわかりやすい
  • ワカリヤスイ
  • 用途によっては高効率
• デメリット
  • 複数回のバックトラックが必要
  • データ量の多いテキストファイルでは極めて非効率的

効果

• Algorithm source code "に返信すると、トップ10のクラシックなアルゴリズムのソースコードを入手できます。
• Algorithm books "と返信すると、古典的なアルゴリズム入門書が表示されます。