Analyse d'algorithme PHP : Comment utiliser un algorithme de programmation dynamique pour résoudre le problème de sous-chaîne palindrome la plus longue ?

Analyse d'algorithme PHP : Comment utiliser un algorithme de programmation dynamique pour résoudre le problème de sous-chaîne palindrome le plus long ?

La programmation dynamique est une idée d'algorithme couramment utilisée qui peut résoudre de nombreux problèmes complexes. L’un d’eux est le problème de la sous-chaîne palindrome la plus longue, qui consiste à trouver la longueur de la sous-chaîne palindrome la plus longue dans une chaîne. Cet article explique comment utiliser PHP pour écrire un algorithme de programmation dynamique afin de résoudre ce problème et fournit des exemples de code spécifiques.

Tout d’abord, définissons la sous-chaîne palindrome la plus longue. Une chaîne palindrome fait référence à une chaîne qui lit la même chose vers l'avant et vers l'arrière, tandis qu'une sous-chaîne palindrome est une chaîne palindrome continue dans la chaîne d'origine. Par exemple, dans la chaîne « level », « eve » est une sous-chaîne palindrome.

Pour résoudre le problème de sous-chaîne palindrome la plus longue, nous pouvons utiliser l'idée d'un algorithme de programmation dynamique. Plus précisément, nous pouvons utiliser un tableau bidimensionnel dp pour indiquer si chaque sous-chaîne de la chaîne est une chaîne palindrome. dpi indique si la sous-chaîne formée du i-ème caractère au j-ème caractère est une chaîne palindrome. Si dpi est vrai, alors la sous-chaîne du i-ème caractère au j-ème caractère est une sous-chaîne palindrome.

Ensuite, nous devons trouver l'équation de transition d'état, c'est-à-dire comment déduire la valeur de dpi+1 en fonction du dpi connu. D'après les propriétés des chaînes palindromes, nous savons que si dpi est vrai, alors la valeur de dpi+1 dépend du fait que le i+1ème caractère et le j+1ème caractère sont égaux. S'ils sont égaux, il vous suffit alors de déterminer si la sous-chaîne du i+1ème caractère au jème caractère est une chaîne palindrome, c'est-à-dire la valeur de dpi+1. Sinon, dpi+1 est faux.

Avec l'équation de transition d'état en main, nous pouvons commencer à écrire du code PHP pour résoudre le problème de sous-chaîne palindrome le plus long.

function longestPalindrome($s) {
    $n = strlen($s);
    $dp = array_fill(0, $n, array_fill(0, $n, false)); // 初始化dp数组，默认都为false

    // 初始化最长回文子串的起始位置和长度
    $start = 0;
    $maxLen = 1;

    // 单个字符都是回文子串
    for ($i = 0; $i < $n; $i++) {
        $dp[$i][$i] = true;
    }

    // 根据状态转移方程计算dp数组
    for ($j = 1; $j < $n; $j++) {
        for ($i = 0; $i < $j; $i++) {
            if ($s[$i] == $s[$j]) {
                if ($j - $i <= 2 || $dp[$i + 1][$j - 1]) {
                    $dp[$i][$j] = true;
                    if ($j - $i + 1 > $maxLen) {
                        $maxLen = $j - $i + 1;
                        $start = $i;
                    }
                }
            }
        }
    }

    return substr($s, $start, $maxLen); // 返回最长回文子串
}

// 测试示例
$str = "babad";
echo longestPalindrome($str);

Dans le code ci-dessus, nous définissons une fonctionlongestPalindrome pour résoudre le problème de sous-chaîne palindrome le plus long. La fonction accepte une chaîne $s comme paramètre et renvoie la sous-chaîne palindrome la plus longue. Dans la fonction, nous initialisons d'abord le tableau dp et marquons les caractères individuels comme sous-chaînes palindromes. Ensuite, calculez le tableau dp selon l'équation de transition d'état. Enfin, nous renvoyons la sous-chaîne palindrome la plus longue en fonction de la position de départ et de la longueur.

Dans l'exemple de code, notre chaîne de test est "babad" et le résultat de sortie est "bab", qui est la sous-chaîne palindrome la plus longue.

En utilisant un algorithme de programmation dynamique, nous pouvons résoudre efficacement le problème de sous-chaîne palindrome le plus long. J'espère que cet article sera utile pour comprendre et appliquer des algorithmes de programmation dynamique.

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!