Explication détaillée de l'algorithme de sous-séquence commune la plus longue en PHP

Explication détaillée de l'algorithme de sous-séquence commune la plus longue en PHP

La sous-séquence commune la plus longue (LCS) est un algorithme de correspondance de chaînes commun, qui est principalement utilisé pour comparer la similarité de deux chaînes. En PHP, l'algorithme LCS peut être implémenté grâce à l'idée de programmation dynamique. Le principe et l'implémentation du code de l'algorithme seront présentés en détail ci-dessous.

1. Principe de l'algorithme
   L'idée centrale de l'algorithme de sous-séquence commune la plus longue est que pour deux chaînes X et Y, trouver la sous-séquence commune la plus longue L telle que L est une sous-séquence de X et Y et n'existe pas de sous-séquence commune plus long que L. Sous l'idée de programmation dynamique, nous pouvons utiliser un tableau bidimensionnel dpi pour représenter la longueur de la sous-séquence commune la plus longue des i premiers caractères de la chaîne X et des j premiers caractères de la chaîne Y.

Plus précisément, nous pouvons suivre les étapes suivantes pour résoudre la sous-séquence commune la plus longue :
1) Initialiser un tableau dp, où dpi représente le maximum des i premiers caractères de la chaîne X et des j premiers caractères de la chaîne Y. La longueur de la longue sous-séquence commune.
2) Parcourez chaque caractère des chaînes X et Y. Si X[i] est égal à Y[j], alors la valeur de dpi peut être obtenue par dpi-1+1 sinon, la valeur de dpi est dpi-1 ; Et dpi Plus grande valeur dans .
3) Enfin, dpm est la longueur de la plus longue sous-séquence commune de chaînes X et Y, où m et n sont les longueurs des chaînes X et Y.

2. Implémentation du code
   Ce qui suit est un exemple de code pour implémenter l'algorithme de sous-séquence commune le plus long en utilisant le langage 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;

Dans le code ci-dessus, nous initialisons d'abord un tableau bidimensionnel dp et ajoutons ses éléments de première ligne et de première colonne sont tous mis à 0. Nous utilisons ensuite deux boucles for imbriquées pour calculer chaque élément du tableau dp. Enfin, nous trouvons la sous-séquence commune la plus longue grâce à un retour en arrière et la renvoyons.

3. Conclusion
   L'algorithme de sous-séquence commune le plus long est un algorithme de correspondance de chaînes efficace adapté à la résolution de problèmes de similarité de chaînes. Grâce à l'idée de programmation dynamique, nous pouvons résoudre la sous-séquence commune la plus longue avec une complexité temporelle de O(m*n). En PHP, nous pouvons utiliser l'exemple de code ci-dessus pour implémenter cet algorithme et obtenir la sous-séquence commune la plus longue de deux chaînes.

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!