Idées de conception d'algorithmes PHP : comment parvenir à une solution efficace au problème de sous-séquence commune maximale ?

Idées de conception d'algorithmes PHP : Comment parvenir à une solution efficace au problème de sous-séquence commune maximale ?

La sous-séquence commune la plus longue (LCS) est le problème de trouver la sous-séquence identique la plus longue dans deux chaînes. Dans les applications pratiques, LCS est largement utilisé dans des domaines tels que la comparaison de similarité de texte, le contrôle de version et la comparaison de séquences d'ADN. Cet article présentera une solution efficace pour résoudre ce problème et fournira des exemples de code spécifiques.

Idée d'algorithme :

La programmation dynamique est une méthode courante pour résoudre les problèmes LCS. Le problème LCS a la propriété de sous-structure optimale, c'est-à-dire que la sous-séquence commune la plus longue de deux séquences peut être construite par la sous-séquence commune la plus longue du sous-problème. Selon cette propriété, une méthode de programmation dynamique peut être utilisée pour résoudre le problème LCS.

Les étapes spécifiques de l'algorithme sont les suivantes :

1. Créez un tableau bidimensionnel dpm+1, où m et n sont respectivement les longueurs des deux chaînes d'entrée.

   • dpi représente la longueur du LCS entre les i premiers caractères de la première chaîne et les j premiers caractères de la deuxième chaîne.
2. Initialisez la première ligne et la première colonne du tableau dp à 0, c'est-à-dire dpi=dp0=0.

3. Parcourez chaque caractère de deux chaînes, pour le i-ème caractère de la première chaîne et le j-ème caractère de la deuxième chaîne :

   • Si les deux caractères sont égaux (c'est-à-dire le premier caractère Le i-ème caractère de la chaîne est égal au j-ème caractère de la deuxième chaîne), alors dpi = dpi-1 + 1.
   • Si les deux caractères ne sont pas égaux, alors dpi = max(dpi-1, dpi), c'est-à-dire la plus grande valeur du LCS du caractère précédent et du caractère suivant est prise.
4. Après avoir parcouru les deux chaînes, le dpm obtenu est la longueur de la sous-séquence commune la plus longue.
5. Selon le résultat du tableau dp, la sous-séquence commune la plus longue peut être obtenue en retour en arrière. À partir de dpm, déplacez-vous vers le coin supérieur gauche. Si dpi est égal à dpi-1 + 1, cela signifie que le caractère actuel appartient à LCS. Ajoutez le caractère à la séquence de résultats et déplacez-vous vers le coin supérieur gauche.

Exemple de code :

fonction la plus longueCommonSubsequence($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";
$str2 = "BDCAB";
$lcs = la plus longueCommonSubsequence( $str1, $str2);
echo "Chaînes d'entrée : $str1 et $str2
";
echo "La sous-séquence commune la plus longue est : $lcs
";
?>

Le Le code ci-dessus affichera :

Chaînes d'entrée : ABCBDAB et BDCAB
La sous-séquence commune la plus longue est : BCBA

Conclusion :

Cet article présente l'idée et le code PHP spécifique d'utiliser un algorithme de programmation dynamique pour résoudre le problème de sous-séquence commune maximale Exemple. En utilisant la programmation dynamique, les problèmes LCS peuvent être résolus efficacement. La complexité temporelle de cet algorithme est O(m*n), où m et n sont respectivement les longueurs des deux chaînes d'entrée. Dans les applications pratiques, l'algorithme peut être optimisé en fonction des besoins, par exemple en utilisant des techniques telles que les tableaux roulants pour réduire la complexité spatiale.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!