Echo
0%

最长回文子串问题解法

发表于 更新于 分类于

最长回文子串问题解法

暴力求解

找出所有子串，依次判断是不是回文子串即可，时间复杂度n^3，大概率导致一些测试点超时。

中心扩展法

依次将每一个位置作为中心，向两侧扩展，直到不满足回文条件位置，找出最大的长度。

但是要注意每个位置要考虑两种情况：

  • 奇数长度如 aba
  • 偶数长度如 abba

所以每个位置需要按照两种方式分别进行扩展

时间复杂度n^2

动态规划算法

状态转移方程

dp[i,j]=

  • dp[i+1,j-1],str[i]=str[j]
  • 0,str[i]!=str[j]

其中dp[j][j]==1含义为从i到j的子串为回文子串

/**
 * @brief 动态规划算法求解最长回文子串
 *
 * @param s
 * @return int
 */
int dp(string s)
{
    int n = s.size();
    if (n < 1)
    {
        return n;
    }
    int longest = 1;                           //记录最长长度
    int start = 0;                             //开始
    vector<vector<int>> dp(n, vector<int>(n)); // n*n向量
    // dp[i][j]=1代表从i到j是回文串
    for (int i = 0; i < n; i++)
    {
        dp[i][i] = 1; //对角线为1及一个字符长度的回文子串
        // aa bb 这种两个的回文串
        if (i < n - 1)
        {
            if (s[i] == s[i + 1])
            {
                dp[i][i + 1] = 1;
                start = i;
                longest = 2; //当前长度为2
            }
        }
    }
    for (int l = 3; l <= n; l++)
    {
        for (int i = 0; i < n - l + 1; i++) //长度为l时的起始点
        {
            int j = l + i - 1; //长度为l时的终点
            if (s[i] == s[j] && dp[i + 1][j - 1] == 1)
            {
                dp[i][j] = 1;
                start = i;
                longest = l;
            }
        }
    }
    return longest;
}

马拉车算法

  1. 将字符串扩展为奇数位，每两个字符之间插入一个#，并在首位插入两个不一样的其他字符，来防止越界如abc可变为$#a#b#c#^
  2. 进行马拉车算法，思路参考了知乎Manacher算法
/**
 * @brief 马拉车算法求解最长回文子串
 *
 * @param s 字符串
 * @return int 长度
 */
int Manacher(string s)
{
    s = preProcess(s);
    vector<int> p(s.size(), 0); // p[i]用于存放以i为中心的回文子串长度
    int center = 0, right = 0;  //当前对称子串的中心及右边界
    for (int i = 1; i < s.size() - 1; i++)
    {
        int i_mirror = 2 * center - i; // i的对称位置
        if (right > i)
        {
            p[i] = min(right - i, p[i_mirror]); //防止超出右边界，超出后就不一定是p[i]=p[i_mirror]了
        }
        else
        {
            p[i] = 0; //如果等于R
        }
        //在上述基础上进行中心扩展
        while (s[i + 1 + p[i]] == s[i - 1 - p[i]])
        {
            p[i]++;
        }
        //需要更新边界和中心基准
        if (i + p[i] > right)
        {
            center = i;
            right = i + p[i];
        }
    }
    return *max_element(p.begin(), p.end()); //注意返回的是迭代器，所以需要用*取值
}

整体代码

#include <bits/stdc++.h>

using namespace std;

/**
 * @brief 字符串预处理，插入间隔符号
 *
 * @param s 待处理字符串
 * @return string 处理完成的字符串
 */
string preProcess(string s)
{
    int n = s.length();
    string temp = "^"; //以^开头
    if (n == 0)
    {
        temp += "$";
        return temp;
    }
    for (int i = 0; i < n; i++)
    {

        temp += "#"; //以#分割
        temp += s[i];
    }
    temp += "#$"; //以$结尾
    return temp;
}
/**
 * @brief 马拉车算法求解最长回文子串
 *
 * @param s 字符串
 * @return int 长度
 */
int Manacher(string s)
{
    s = preProcess(s);
    vector<int> p(s.size(), 0); // p[i]用于存放以i为中心的回文子串长度
    int center = 0, right = 0;  //当前对称子串的中心及右边界
    for (int i = 1; i < s.size() - 1; i++)
    {
        int i_mirror = 2 * center - i; // i的对称位置
        if (right > i)
        {
            p[i] = min(right - i, p[i_mirror]); //防止超出右边界，超出后就不一定是p[i]=p[i_mirror]了
        }
        else
        {
            p[i] = 0; //如果等于R
        }
        //在上述基础上进行中心扩展
        while (s[i + 1 + p[i]] == s[i - 1 - p[i]])
        {
            p[i]++;
        }
        //需要更新边界和中心基准
        if (i + p[i] > right)
        {
            center = i;
            right = i + p[i];
        }
    }
    return *max_element(p.begin(), p.end()); //注意返回的是迭代器，所以需要用*取值
}
/**
 * @brief 动态规划算法求解最长回文子串
 *
 * @param s
 * @return int
 */
int dp(string s)
{
    int n = s.size();
    if (n < 1)
    {
        return n;
    }
    int longest = 1;                           //记录最长长度
    int start = 0;                             //开始
    vector<vector<int>> dp(n, vector<int>(n)); // n*n向量
    // dp[i][j]=1代表从i到j是回文串
    for (int i = 0; i < n; i++)
    {
        dp[i][i] = 1; //对角线为1及一个字符长度的回文子串
        // aa bb 这种两个的回文串
        if (i < n - 1)
        {
            if (s[i] == s[i + 1])
            {
                dp[i][i + 1] = 1;
                start = i;
                longest = 2; //当前长度为2
            }
        }
    }
    for (int l = 3; l <= n; l++)
    {
        for (int i = 0; i < n - l + 1; i++) //长度为l时的起始点
        {
            int j = l + i - 1; //长度为l时的终点
            if (s[i] == s[j] && dp[i + 1][j - 1] == 1)
            {
                dp[i][j] = 1;
                start = i;
                longest = l;
            }
        }
    }
    return longest;
}
int main()
{
    string a;
    getline(cin, a);
    cout << dp(a);
}