Penjelasan terperinci tentang algoritma urutan biasa terpanjang dalam PHP

Penjelasan terperinci tentang algoritma urutan biasa terpanjang dalam PHP

Jujukan biasa terpanjang (LCS) ialah algoritma padanan rentetan biasa, yang digunakan terutamanya untuk membandingkan persamaan dua rentetan. Dalam PHP, algoritma LCS boleh dilaksanakan melalui idea pengaturcaraan dinamik Prinsip dan pelaksanaan kod algoritma akan diperkenalkan secara terperinci di bawah.

1. Prinsip algoritma
   Idea teras algoritma urutan sepunya terpanjang ialah untuk mana-mana dua rentetan X dan Y, cari urutan sepunya terpanjang L supaya L ialah susulan bagi X dan Y dan tidak wujud Susulan sepunya. lebih lama daripada L. Di bawah idea pengaturcaraan dinamik, kita boleh menggunakan dpi tatasusunan dua dimensi untuk mewakili panjang urutan sepunya terpanjang bagi aksara i pertama rentetan X dan aksara j pertama rentetan Y.

Secara khusus, kita boleh mengikuti langkah berikut untuk menyelesaikan urutan sepunya terpanjang:
1) Mulakan tatasusunan dp, dengan dpi mewakili maksimum aksara i pertama rentetan X dan aksara j pertama rentetan Y Panjangnya susulan biasa yang panjang.
2) Lintas setiap aksara rentetan X dan Y. Jika X[i] bersamaan dengan Y[j], maka nilai dpi boleh diperolehi dengan dpi-1+1 jika tidak, nilai dpi ialah dpi-1; dan dpi Nilai yang lebih besar dalam .
3) Akhir sekali, dpm ialah panjang bagi urutan sepunya terpanjang bagi rentetan X dan Y, dengan m dan n ialah panjang rentetan X dan Y.

2. Pelaksanaan kod
   Berikut ialah contoh kod untuk melaksanakan algoritma urutan biasa terpanjang menggunakan bahasa PHP:

function LCS($str1, $str2)
{
    $m = strlen($str1);
    $n = strlen($str2);

    $dp = array();
    for ($i = 0; $i <= $m; $i++) {
        $dp[$i][0] = 0;
    }
    for ($j = 0; $j <= $n; $j++) {
        $dp[0][$j] = 0;
    }

    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($str1[$i - 1] == $str2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
            } else {
                $dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
            }
        }
    }

    $lcs = '';
    $i = $m;
    $j = $n;
    while ($i > 0 && $j > 0) {
        if ($str1[$i - 1] == $str2[$j - 1]) {
            $lcs = $str1[$i - 1] . $lcs;
            $i--;
            $j--;
        } elseif ($dp[$i - 1][$j] > $dp[$i][$j - 1]) {
            $i--;
        } else {
            $j--;
        }
    }

    return $lcs;
}

$str1 = "abcdefg";
$str2 = "bcedgh";

$lcs = LCS($str1, $str2);
echo "最长公共子序列: " . $lcs;

Dalam kod di atas, kami mula-mula memulakan dp tatasusunan dua dimensi dan menambah baris pertama dan elemen lajur pertama semuanya ditetapkan kepada 0. Kami kemudian menggunakan dua gelung bersarang untuk mengira setiap elemen dalam tatasusunan dp. Akhir sekali, kami mencari urutan biasa terpanjang melalui penjejakan ke belakang dan mengembalikannya.

3. Kesimpulan
   Algoritma urutan lazim terpanjang ialah algoritma pemadanan rentetan yang cekap sesuai untuk menyelesaikan masalah persamaan rentetan. Melalui idea pengaturcaraan dinamik, kita boleh menyelesaikan urutan sepunya terpanjang dengan kerumitan masa O(m*n). Dalam PHP, kita boleh menggunakan contoh kod di atas untuk melaksanakan algoritma ini dan mendapatkan urutan biasa terpanjang bagi dua rentetan.

Atas ialah kandungan terperinci Penjelasan terperinci tentang algoritma urutan biasa terpanjang dalam PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!