Principe de mise en œuvre de l'algorithme de sous-chaîne commune la plus longue en PHP

Le principe d'implémentation de l'algorithme de sous-chaîne commune la plus longue en PHP

La sous-chaîne commune la plus longue (Longest Common Substring) est un algorithme de correspondance de chaîne couramment utilisé, utilisé pour trouver la sous-chaîne continue identique la plus longue dans deux chaînes. En PHP, nous pouvons utiliser un algorithme de programmation dynamique pour trouver la sous-chaîne commune la plus longue.

Ci-dessous, nous présenterons en détail le principe de mise en œuvre de l'algorithme de sous-chaîne commun le plus long en PHP et joindrons des exemples de code pertinents.

1. Principe de l'algorithme de programmation dynamique

L'algorithme de programmation dynamique est utilisé pour résoudre des problèmes avec des sous-problèmes qui se chevauchent et des propriétés de sous-structure optimales. Le problème de sous-chaîne commune le plus long satisfait ces conditions et peut donc être résolu à l’aide d’un algorithme de programmation dynamique.

Le problème de la sous-chaîne commune la plus longue peut être formalisé comme : étant donné deux chaînes S1 et S2, trouver leur sous-chaîne commune la plus longue LCS.

L'idée centrale de l'algorithme de programmation dynamique est de diviser le problème en plusieurs sous-problèmes et de trouver la solution optimale au problème d'origine en résolvant les solutions optimales des sous-problèmes. Pour le problème de sous-chaîne commun le plus long, nous pouvons le diviser en sous-problèmes plus petits. Pour les i premiers caractères de la chaîne S1 et les j premiers caractères de la chaîne S2, nous pouvons déterminer si S1[i] et S2[j] sont égaux. S'ils sont égaux, nous pouvons obtenir un nouveau sous-problème, c'est-à-dire. résoudre le problème de S1 La sous-chaîne commune la plus longue des i-1 premiers caractères et des j-1 premiers caractères de S2. Si elle n’est pas égale, la longueur de la sous-chaîne commune la plus longue est 0.

Grâce au processus de division ci-dessus, nous pouvons construire un tableau bidimensionnel pour une solution de programmation dynamique. Les lignes du tableau représentent les caractères de S1, les colonnes représentent les caractères de S2 et chaque cellule représente la longueur de la sous-chaîne commune la plus longue des i premiers caractères de S1 et des j premiers caractères de S2. Enfin, la cellule dans le coin inférieur droit du tableau correspond à la longueur de la sous-chaîne commune la plus longue recherchée.

2. Implémentation de l'algorithme de sous-chaîne commune la plus longue

Ci-dessous, nous donnons l'implémentation du code de l'algorithme de sous-chaîne commune la plus longue en PHP :

function longestCommonSubstring($str1, $str2) {
    $length1 = strlen($str1);
    $length2 = strlen($str2);

    // 初始化二维数组
    $dp = array();
    for ($i = 0; $i <= $length1; $i++) {
        $dp[$i] = array();
        for ($j = 0; $j <= $length2; $j++) {
            $dp[$i][$j] = 0;
        }
    }

    $maxLen = 0;
    $endIndex = 0;

    // 动态规划求解
    for ($i = 1; $i <= $length1; $i++) {
        for ($j = 1; $j <= $length2; $j++) {
            if ($str1[$i - 1] == $str2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
                if ($dp[$i][$j] > $maxLen) {
                    $maxLen = $dp[$i][$j];
                    $endIndex = $i - 1;
                }
            }
        }
    }

    // 根据最长公共子串的长度和结束索引截取子串
    $longestSubstring = substr($str1, $endIndex - $maxLen + 1, $maxLen);

    return $longestSubstring;
}

// 示例
$str1 = "ABCABC";
$str2 = "BABCAB";

$result = longestCommonSubstring($str1, $str2);
echo "最长公共子串：".$result;

Dans le code ci-dessus, nous calculons d'abord les longueurs des chaînes S1 et S2 et les initialisons A le tableau bidimensionnel $dp est utilisé pour stocker les résultats de la programmation dynamique. Ensuite, parcourez S1 et S2 via une double boucle et mettez à jour la valeur du tableau $dp selon que les caractères actuels sont égaux ou non.

Enfin, en fonction de la longueur et de l'index de fin de la sous-chaîne commune la plus longue, utilisez la fonction substr pour intercepter la sous-chaîne commune la plus longue et la renvoyer.

3. Résumé

L'algorithme de sous-chaîne commune la plus longue est un algorithme de correspondance de chaînes couramment utilisé qui est utilisé pour trouver la sous-chaîne continue identique la plus longue dans deux chaînes. En PHP, nous pouvons utiliser un algorithme de programmation dynamique pour trouver la sous-chaîne commune la plus longue. En construisant un tableau bidimensionnel pour une solution de programmation dynamique, la sous-chaîne commune la plus longue peut être trouvée efficacement.

Grâce aux principes et aux exemples de code présentés dans cet article, je pense que les lecteurs auront une compréhension plus approfondie de la mise en œuvre de l'algorithme de sous-chaîne commune le plus long en PHP. J'espère que cet article sera utile aux lecteurs pour résoudre les problèmes de correspondance de 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!