Bagaimana untuk melaksanakan algoritma pemadanan rentetan dengan PHP

Cara melaksanakan algoritma pemadanan rentetan dalam PHP

Pemadanan rentetan merupakan salah satu isu penting dalam sains komputer Ia sering digunakan dalam enjin carian, penyunting teks, perlombongan data dan bidang lain. Dalam artikel ini, kami akan memperkenalkan cara menggunakan PHP untuk melaksanakan dua algoritma padanan rentetan biasa: padanan kekerasan kasar dan algoritma KMP.

1. Algoritma pemadanan brute force

Algoritma pemadanan brute force ialah algoritma pemadanan rentetan yang paling mudah dan paling intuitif. Ideanya sangat mudah, iaitu, menyemak aksara demi aksara dalam rentetan utama sama ada ia sepadan dengan rentetan corak. Jika tiada padanan, alihkan satu aksara ke belakang dan mulakan padanan semula jika terdapat padanan, teruskan padanan aksara seterusnya sehingga padanan ditemui atau keseluruhan rentetan utama dilalui.

Berikut ialah contoh kod untuk algoritma pemadanan brute force yang dilaksanakan dalam 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. Algoritma KMP

Algoritma KMP ialah algoritma pemadanan rentetan yang cekap yang menggunakan maklumat rentetan corak itu sendiri untuk mengurangkan operasi pemadanan yang tidak perlu. Idea terasnya ialah semasa proses pemadanan, apabila ketidakpadanan ditemui, titik permulaan padanan baharu ditentukan berdasarkan bahagian yang dipadankan, bukannya bermula dari aksara seterusnya rentetan utama setiap kali.

Berikut ialah contoh kod algoritma KMP yang dilaksanakan dalam PHP:

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;

Melalui contoh di atas, kita dapat melihat bahawa berbanding dengan algoritma pemadanan brute force, algoritma KMP mengurangkan bilangan perbandingan aksara yang tidak diperlukan dan meningkatkan kecekapan padanan rentetan.

Ringkasan:

Artikel ini memperkenalkan cara menggunakan PHP untuk melaksanakan algoritma pemadanan rentetan, termasuk algoritma pemadanan brute force dan algoritma KMP. Algoritma pemadanan kuasa kasar adalah mudah dan intuitif, tetapi mempunyai kecekapan yang rendah manakala algoritma KMP meningkatkan kecekapan pemadanan dengan menggunakan maklumat rentetan corak itu sendiri. Dalam aplikasi praktikal, mengikut senario dan keperluan yang berbeza, anda boleh memilih algoritma pemadanan rentetan yang sesuai untuk meningkatkan prestasi program.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma pemadanan rentetan dengan PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!