PHPで文字列マッチングアルゴリズムを実装する方法

PHP を使用して文字列マッチング アルゴリズムを実装する方法

文字列マッチングはコンピューター サイエンスにおける重要な問題の 1 つであり、検索エンジン、テキスト エディター、データ マイニングなどの分野でよく使用されます。この記事では、PHP を使用して、ブルート フォース マッチングと KMP アルゴリズムという 2 つの一般的な文字列マッチング アルゴリズムを実装する方法を紹介します。

1. 暴力的なマッチング アルゴリズム

暴力的なマッチング アルゴリズムは、最も単純で直感的な文字列マッチング アルゴリズムです。その考え方は非常に単純です。つまり、メイン文字列内の 1 文字ずつ、パターン文字列と一致するかどうかをチェックします。一致する文字がない場合は、1 文字戻して再度一致を開始します。一致する場合は、一致が見つかるかメイン文字列全体が検索されるまで、次の文字の一致を続けます。

以下は、PHP で実装されたブルート フォース マッチング アルゴリズムのサンプル コードです。

function bruteForce($str, $pattern) {
    $n = strlen($str);
    $m = strlen($pattern);
    
    for ($i = 0; $i <= $n - $m; $i++) {
        $j = 0;
        while ($j < $m && $str[$i+$j] == $pattern[$j]) {
            $j++;
        }
        
        if ($j == $m) {
            return $i; // 匹配成功，返回匹配的起始位置
        }
    }
    
    return -1; // 匹配失败，返回-1
}

$str = "Hello, World!";
$pattern = "World";
$position = bruteForce($str, $pattern);
echo "The position of the pattern is: " . $position;

2. KMP アルゴリズム

KMP アルゴリズムは効率的な文字列です。マッチング アルゴリズム 。パターン文字列自体の情報を使用して、不要なマッチング操作を削減します。その中心的な考え方は、マッチング プロセス中に不一致が見つかった場合、毎回メイン文字列の次の文字から開始するのではなく、一致した部分に基づいて新しいマッチング開始点が決定されるということです。

以下は、PHP で実装された KMP アルゴリズムのサンプル コードです:

function calculateNext($pattern) {
    $m = strlen($pattern);
    $next[0] = -1;
    $i = 0;
    $j = -1;
    
    while ($i < $m - 1) {
        if ($j == -1 || $pattern[$i] == $pattern[$j]) {
            $i++;
            $j++;
            $next[$i] = $j;
        } else {
            $j = $next[$j];
        }
    }
    
    return $next;
}

function kmp($str, $pattern) {
    $n = strlen($str);
    $m = strlen($pattern);
    $next = calculateNext($pattern);
    $i = 0;
    $j = 0;
    
    while ($i < $n && $j < $m) {
        if ($j == -1 || $str[$i] == $pattern[$j]) {
            $i++;
            $j++;
        } else {
            $j = $next[$j];
        }
    }
    
    if ($j == $m) {
        return $i - $j; // 匹配成功，返回匹配的起始位置
    }
    
    return -1; // 匹配失败，返回-1
}

$str = "Hello, World!";
$pattern = "World";
$position = kmp($str, $pattern);
echo "The position of the pattern is: " . $position;

上記の例を通じて、KMP アルゴリズムはブルート アルゴリズムと比較して不必要な文字比較の数を減らしていることがわかります。強制マッチング アルゴリズム。文字列マッチングの効率が向上しました。

概要:

この記事では、PHP を使用して、ブルート フォース マッチング アルゴリズムや KMP アルゴリズムなどの文字列マッチング アルゴリズムを実装する方法を紹介します。ブルートフォースマッチングアルゴリズムはシンプルで直感的ですが効率が低いのに対し、KMPアルゴリズムはパターン文字列そのものの情報を利用することでマッチング効率を向上させます。実際のアプリケーションでは、さまざまなシナリオやニーズに応じて、適切な文字列一致アルゴリズムを選択して、プログラムのパフォーマンスを向上させることができます。

以上がPHPで文字列マッチングアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。