最长回文子串

介绍

最长回文子串（Longest Palindromic Substring）问题 就是找到给定字符串中的最长连续子串，而且这个子串是一个回文字符串。它与 最长回文子序列（Longest Palindromic Subsequence）问题 不同，最长回文子序列不要求子序列在原来的序列中是位置连续的。

最长回文子串

最长回文子序列

用 $\texttt{dp}[i][j]$ 表示子串 $S_{i\dots j}$ 中包含的最长回文子序列，则有

$$ \texttt{dp}[i][j]=\begin{cases} 2+\texttt{dp}[i+1][j-1]&(S[i]=S[j])\\ \max(\texttt{dp}[i+1][j],\texttt{dp}[i][j-1])&(\text{otherwise}) \end{cases} $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


def longest_palindrome_subsequence(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for r in range(n):
        dp[r][r] = 1
        for l in reversed(range(r)):
            if s[l] == s[r]:
                dp[l][r] = 2 + dp[l + 1][r - 1]
            else:
                dp[l][r] = max(dp[l + 1][r], dp[l][r - 1])

    return dp[0][n - 1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


int longest_palindrome_subsequence(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n));

    for (int r = 0; r < n; ++r) {
        dp[r][r] = 1;
        for (int l = r - 1; l >= 0; --l) {
            if (s[l] == s[r]) {
                dp[l][r] = 2 + dp[l + 1][r - 1];
            } else {
                dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
            }
        }
    }

    return dp[0][n - 1];
}

例题