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);
}