Bagaimana untuk melaksanakan algoritma pemadanan rentetan dengan PHP

PHPz
Lepaskan: 2023-07-08 08:16:02
asal
1519 orang telah melayarinya

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;
Salin selepas log masuk
  1. 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;
Salin selepas log masuk

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!

Label berkaitan:
sumber:php.cn
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan