ホームページ > バックエンド開発 > PHPチュートリアル > PHP は、パターン検索用の単純なアルゴリズム (文字列一致アルゴリズム) を実装しています。

PHP は、パターン検索用の単純なアルゴリズム (文字列一致アルゴリズム) を実装しています。

藏色散人
リリース: 2023-04-05 18:46:01
オリジナル
2813 人が閲覧しました

テキスト txt [0..n-1] とパターン pat [0..m-1] を指定して、検索する関数を作成します (char pat [ ]、char txt []) 、txt 内の pat [] [] の出現箇所をすべて出力します。 n> m と仮定できます。

例:

输入:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
输出: Pattern found at index 10

输入:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
输出: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12
ログイン後にコピー

PHP は、パターン検索用の単純なアルゴリズム (文字列一致アルゴリズム) を実装しています。

パターン検索は、コンピューター サイエンスにおける重要な問題です。メモ帳、ワード ファイル、ブラウザ、データベースで文字列を検索すると、パターン検索アルゴリズムが使用されて検索結果が表示されます。

単純なパターン検索:
テキスト内でパターンを 1 つずつスライドさせ、一致するかどうかを確認します。一致するものが見つかった場合は、もう一度 1 をスライドして、後続の一致を確認します。

PHP コード:

<?php 
// 朴素模式搜索算法
  
function search($pat, $txt) 
{ 
    $M = strlen($pat); 
    $N = strlen($txt); 
  
    for ($i = 0; $i <= $N - $M; $i++) 
    { 
  
        // 对于当前索引i,请检查模式匹配
        for ($j = 0; $j < $M; $j++) 
            if ($txt[$i + $j] != $pat[$j]) 
                break; 
  
        // if pat[0...M-1] =  
        // txt[i, i+1, ...i+M-1] 
        if ($j == $M)  
            echo "Pattern found at index ", $i."\n"; 
    } 
} 
  
    $txt = "AABAACAADAABAAABAA"; 
    $pat = "AABA"; 
    search($pat, $txt);
ログイン後にコピー

出力:

Pattern found at index 0 
Pattern found at index 9 
Pattern found at index 13
ログイン後にコピー

最良のシナリオは何ですか?

パターンの最初の文字がテキスト内にまったく存在しない場合が最良のケースです。

filter_none
brightness_4
txt[] = "AABCCAADDEE"; 
pat[] = "FAA";
ログイン後にコピー

最良の場合の比較回数は O(n) です。

最悪のシナリオは何ですか?

1) テキストとパターンの文字がすべて同じ場合。

filter_none
brightness_4
txt[] = "AAAAAAAAAAAAAAAAAA"; 
pat[] = "AAAAA";
ログイン後にコピー

2) 最悪のケースは、最後の文字が異なる場合にも発生します。

filter_none
brightness_4
txt[] = "AAAAAAAAAAAAAAAAAB"; 
pat[] = "AAAAB";
ログイン後にコピー

最悪の場合の比較数は O(m *(n-m 1)) です。繰り返し文字を含む文字列が英語のテキストに現れることはほとんどありませんが、他のアプリケーション (バイナリ テキストなど) では現れる可能性があります。

関連する推奨事項: 「PHP チュートリアル

以上がPHP は、パターン検索用の単純なアルゴリズム (文字列一致アルゴリズム) を実装しています。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

関連ラベル:
ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート