区间动态规划-最长回文子串

问题：给定一个字符串，求出字符串中最长回文子串。
例如：
input “babad” output”bab”

对于最长回文子串问题，动态规划方法的核心思想是：

状态定义：定义一个二维数组 dp[i][j]，其中 dp[i][j] 表示字符串中从索引 i 到 j 的子串是否为回文串。
状态转移：状态 dp[i][j] 的值依赖于 dp[i+1][j-1] 的值，即内部子串的回文性质，以及 s[i] 和 s[j]（字符串中第 i 和第 j 个字符）是否相等。简单地说，如果内部子串是回文且当前考虑的两端字符相等，则当前子串也是回文。
初始化：单个字符总是回文串，所以对于所有 i，dp[i][i] 是 true。对于长度为 2 的子串，只需检查两个字符是否相同。
结果构建：通过遍历所有可能的子串并更新最长回文子串的记录，最终得到所求的最长回文子串。

在解决这种类型的动态规划问题时，通常需要两层循环遍历所有可能的子区间，并计算每个子区间的属性。这种方法在处理字符串相关的问题，特别是涉及子串属性的问题时非常有效。

这个动态规划方法的时间复杂度是 O(N^2)，其中 N 是字符串的长度。对于每个子串，我们只需要 O(1) 的时间来判断它是否是回文串。尽管这种方法在理论上是有效的，但在实际应用中，特别是对于较长的字符串，中心扩展法或Manacher算法可能会有更好的性能。

/**************************************************************** 
 * Description: 动态规划求最长回文子串
 * Author: Alex Li
 * Date: 2023-11-20 15:52:10
 * LastEditTime: 2023-11-20 16:56:35
****************************************************************/
#include <iostream>
#include <string>
#include <vector>
using namespace std;

string longestPalindrome(string s) {
    int n = s.size();
    if (n == 0) return "";

   //我们使用一个二维布尔数组 dp 来存储信息。如果 s[i...j] 是回文串，则 dp[i][j] 为 true。
    bool  dp[n][n];
    
    string longest = "";
     //外层循环遍历所有可能的子串长度 len，从长度为 1 到 n。
    for (int len = 1; len <= n; len++) {
        //内层循环遍历所有可能的起始位置 start。
        for (int start = 0; start < n; start++) {
            int end = start + len - 1;
            if (end >= n) break;
            //如果子串长度为 1（len == 1），则子串是回文因为单个字符总是回文
            //如果子串长度为 2（len == 2），则需要检查这两个字符是否相同（s[start] == s[end]）
            //对于大于2的子串 s[start...end]，如果它的首尾字符相同，并且其内部子串 s[start+1...end-1] 也是回文串，则当前子串是回文串。 
            //(len == 1 || len == 2 || dp[start + 1][end - 1]) 这式子利用了或运算的短路模式，
            //len==1为true就不运算第二项，len==2为true就不运算第三项
            dp[start][end] = (len == 1 || len == 2 || dp[start + 1][end - 1]) && s[start] == s[end];
            

            //如果找到了更长的回文子串，则更新 longest。
            if (dp[start][end] && len > longest.size()) {
                longest = s.substr(start, len);
            }
        }
    }
    return longest;
}

int main() {
    string s;
    cin>>s;
    cout << "Longest Palindromic Substring: " << longestPalindrome(s) << endl;
    return 0;
}

马拉车(Manacher)算法

一、p[i]数组定义

为了解决在偶数回文串没有中心字符，而奇数存在中心字符的问题，对字符串进行预处理，在每个字符之间插入原字符串中不存在的字符，例如’#’或’$’之类的。这样求出的回文子串的长度永远是奇数。
例如：
原字符串为”aba”，处理后为”#a#b#a#”
原字符串为”abba”，处理后为”#a#b#b#a#”
原字符串的最大回文子串是新字符串最大回文子串长度除以2。

我们后面讨论字符串都是经过插入字符后得到的新串

设定p[i]表示以第i个字符为中心向两边扩展的最大回文半径(包括i点)。从左向右依次计算p[i]

例如s=”#a#b#a#b#”

i	1	2	3	4	5	6	7	8	9
str	#	a	#	b	#	a	#	b	#
p[i]	1	2	1	4	1	4	1	2	1

得到p[i]数组后，p[i]-1就是原串以i为中心的最大回文长度。

二、计算p[i]

定义rt表示已经计算过的回文串能到达的最远边界的下一个位置，mid表示rt所对应的最右侧的回文中心。
存在mid+p[i]=rt 如图所示：

已经计算完p[1]~p[i-1]，以mid为中心的回文子串右边界最远能达到rt-1的位置。

i	1	2	3	4	5	6	7	8	9
str	#	a	#	b	#	a	#	b	#
p[i]	1	2	1	4
4=i-1				mid				rt-1	rt

计算p[i]需要分为以下情况：

如果i>=rt，此时已经没有对称性可以利用，令p[i]=1，继续计算。

i	1	2	3	4	5	6	7	8	9
str	#	a	#	b	#	c	#	b	#
p[i]	1	2	1	2	1	1	1	1
				mid		rt		i

如果i<rt，我们可以通过mid的对称点j来计算p[i]，关于j又有两种情况。

1，以j为中心的回文串被包含在以mid为中心的回文串中。

2、以j为中心的回文串没有被包含在以mid为中心的最大回文串中。

代码演示

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-23 15:42:36
 * 最后修改: 2025-01-24 21:22:24
 * 文件描述: Manacher函数用于查找给定字符串中的最长回文子串长度。
 *          该算法巧妙地利用了回文字符串的对称性质，以线性时间复杂度完成查找。
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

int n, m;
string s, str;
int p[2000010];

void Manacher() {
    // 初始化右边界rt、中心点mid和最长回文长度ans。
    int rt = 0, mid = 0, ans = 0;
    
    // 遍历预处理后的字符串数组，i从1开始以避开哨兵。
    for (int i = 1; i < m; i++) {
        // 如果当前点在右边界内，尝试扩展回文半径，否则从最小半径开始。
        if (i < rt) p[i] = min(p[2 * mid - i], rt - i);
        else p[i] = 1;
        
        // 尝试扩展i为中心的回文字符串，更新其半径。
        while (str[i - p[i]] == str[i + p[i]]) p[i]++;
        
        // 如果当前回文字符串的右边界超过了之前的右边界，更新右边界rt和中心点mid。
        if (i + p[i] > rt) {
            rt = i + p[i];
            mid = i;
        }
        
        // 更新最长回文子串的长度。
        ans = max(ans, p[i] - 1);
    }
    
    // 输出最长回文子串的长度。
    cout << ans << endl;
}

int main() {
    // 初始化字符串处理用的特殊字符
    str += '*', str += '#';
    
    // 读取输入字符串
    cin >> s;
    
    // 计算输入字符串的长度
    n = s.length();
    
    // 将输入字符串s转换为特殊格式的字符串str，用于后续的Manacher算法处理
    for (int i = 0; i < n; i++) {
        str += s[i];
        str += '#';
    }
    
    // 在字符串str末尾添加结束标志字符
    str += '^';
     // 计算转换后字符串str的长度
    m = str.length();
    // 调用Manacher算法函数进行处理
    Manacher();
    
    return 0;
}

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

区间动态规划-最长回文子串