Idea reka bentuk algoritma PHP: Bagaimana untuk mencapai penyelesaian yang cekap kepada masalah susulan biasa yang maksimum?

Idea reka bentuk algoritma PHP: Bagaimana untuk mencapai penyelesaian yang cekap kepada masalah susulan biasa yang maksimum?

Longest Common Subsequence (LCS) ialah masalah mencari urutan identik terpanjang dalam dua rentetan. Dalam aplikasi praktikal, LCS digunakan secara meluas dalam bidang seperti perbandingan persamaan teks, kawalan versi dan perbandingan jujukan DNA. Artikel ini akan memperkenalkan penyelesaian yang cekap untuk menyelesaikan masalah ini dan memberikan contoh kod khusus.

Idea algoritma:

Pengaturcaraan dinamik ialah kaedah biasa untuk menyelesaikan masalah LCS. Masalah LCS mempunyai sifat substruktur yang optimum, iaitu, urutan sepunya terpanjang bagi dua jujukan boleh dibina oleh urutan sepunya terpanjang bagi submasalah. Menurut sifat ini, kaedah pengaturcaraan dinamik boleh digunakan untuk menyelesaikan masalah LCS.

Langkah algoritma khusus adalah seperti berikut:

1. Buat tatasusunan dua dimensi dpm+1, dengan m dan n ialah panjang dua rentetan input masing-masing.

   • dpi mewakili panjang LCS antara aksara i pertama rentetan pertama dan aksara j pertama rentetan kedua.
2. Mulakan baris dan lajur pertama tatasusunan dp kepada 0, iaitu, dpi=dp0=0.

3. Gelung setiap aksara dua rentetan, untuk aksara ke-i bagi rentetan pertama dan aksara ke-j bagi rentetan kedua:

   • Jika dua aksara adalah sama (iaitu aksara pertama The ke-i aksara rentetan adalah sama dengan aksara ke-j rentetan kedua), kemudian dpi = dpi-1 + 1.
   • Jika kedua-dua aksara tidak sama, maka dpi = maks(dpi-1, dpi), iaitu nilai yang lebih besar bagi LCS aksara sebelumnya dan aksara seterusnya diambil.
4. Selepas merentasi dua rentetan, dpm yang diperolehi ialah panjang urutan sepunya terpanjang.
5. Menurut hasil tatasusunan dp, urutan lazim terpanjang boleh diperolehi menjejak ke belakang. Bermula dari dpm, beralih ke sudut kiri atas Jika dpi adalah sama dengan dpi-1 + 1, ini bermakna aksara semasa adalah milik LCS.

Contoh kod:

fungsi paling panjangCommonSubsequence($str1, $str2){

$m = strlen($str1);
$n = strlen($str2);
$dp = array();

for($i=0; $i<=$m; $i++){
    $dp[$i] = array_fill(0, $n+1, 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--;
    }
    else if($dp[$i-1][$j] > $dp[$i][$j-1]){
        $i--;
    }
    else{
        $j--;
    }
}

return $lcs;

}

$str1 = "ABCBDAB";
= "ubCAstrB"lc;
BD$str2 $str1, $str2);
echo "Rentetan input: $str1 dan $str2
";
echo "Jujukan biasa terpanjang ialah: $lcs
";
?>

The kod di atas akan mengeluarkan:

Input rentetan: ABCBDAB dan BDCAB
Jujukan biasa terpanjang ialah: BCBA

Kesimpulan:

Artikel ini memperkenalkan idea dan kod PHP khusus menggunakan algoritma pengaturcaraan dinamik untuk menyelesaikan masalah jujukan biasa maksimum Contoh. Dengan menggunakan pengaturcaraan dinamik, masalah LCS boleh diselesaikan dengan cekap. Kerumitan masa algoritma ini ialah O(m*n), di mana m dan n ialah panjang dua rentetan input masing-masing. Dalam aplikasi praktikal, algoritma boleh dioptimumkan mengikut keperluan, seperti menggunakan teknik seperti tatasusunan rolling untuk mengurangkan kerumitan ruang.

Atas ialah kandungan terperinci Idea reka bentuk algoritma PHP: Bagaimana untuk mencapai penyelesaian yang cekap kepada masalah susulan biasa yang maksimum?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!