题解
题目难度：中等难度、经典题目
知识点：字符串、动态数组、动态规划、Manacher法。
##名词解释：
1.子串：由原字符串中任意个连续字符组成的子序列，其长度小于等于原字符串长度。
2.回文：字符对称的文法，有“aba”(单核)和“cabbac”(双核)两种情况。
3.最长回文子串：首先寻找回文子串，其次，判断该回文子串是否为长度最长。
方法一（暴力求解）
思想：从最长的子串开始，遍历所有该原字符串的子串；每找出一个字符串，就判断该字符串是否为回文；子串为回文时，则找到了最长的回文子串，因此结束；反之，则继续遍历。
时间复杂度O(n^3)：遍历字符串子串：嵌套一个循环、O(n^2)， 判断是否为回文：再次嵌套一个循环、O(n^3)。
#include<iostream>
using namespace std;
string longesPlindrome(string s){
if(s.length()<=1) return s;
//i表示子串长度
for(int i=s.length();i>1;i--){
//j表示子串从原字符串那个下标开始
for(int j=0;j<=s.length()-i;j++){
string sub ;
//得到子串
sub=s.substr(j,i);
int count=0;
//判断子串是否为回文字符串
for(int k=0;k<sub.length()/2;k++){
if(sub[k]==sub[sub.length()-k-1]) count++;
}
if(count==sub.length()/2) return sub;
}
}
}
int main(){
string s;
cin>>s;
string sub=longesPlindrome(s);
cout<<sub;
return 0;
} 方法二：中心扩展算法
思想：
步骤一：中心有2种，一种是一个字母（单核），另一种是两个字母之间（双核）。也就是奇数长度子串和偶数长度子串。首先确定中心位置i（遍历所有i的情况），分单核和双核两种情况进行步骤二计算，单核：初始low =i，high=i；双核low=i,high = i+1。
步骤二：确定好中心位置后向两个方向扩展，判断low和high是否不超过原字符串的下限和上限，以及low和high处的字符是否相等，相等则low--、high++继续步骤二。否者返回right-left-1，为以该i为中心时能找到的最长回文字符串。
步骤三：判断该次以i为中心的单核、双核情况下得到的最长长度，以及变量maxLen保存的所求得的最大长度比较，将最大值赋值给maxLen变量，并且得到此时最长回文子串sub。
步骤四：遍历完所有中心i后，sub字符串为得到的最长回文子串。
时间复杂度：遍历字符：一层循环、O(n-1)；找以当前字符为中心的最长回文子串：嵌套两个独立循环、O(2n*(n-1)) = O(n^2)。
#include<iostream>
using namespace std;
int max(int a,int b){
return a>b ? a: b;
}
int expandAroundCenter(string s,int left, int right){
while(left>=0 && right<s.size() && s[left]==s[right]){
--left;
++right;
}
return right-left-1;
}
string longestPalindrome(string s) {
if(s.empty())
return "";
int startIndex=0;
int maxLen=1;
for(int i=0;i<s.size();++i){
int len1=expandAroundCenter(s,i,i);
int len2=expandAroundCenter(s,i,i+1);
int len=max(len1,len2);
if(len>maxLen){
startIndex=i-(len-1)/2;
maxLen=len;
}
}
return s.substr(startIndex,maxLen);
}
int main(){
string s;
cin>>s;
string sub=longestPalindrome(s);
cout<<sub;
return 0;
}方法三：动态规划：
i，j分别是子串的头索引和尾索引。
对于字符串str，假设dp[i,j]=1表示str[i...j]是回文子串，那个必定存在dp[i+1,j-1]=1。这样最长回文子串就能分解成一系列子问题，可以利用动态规划求解了。首先构造状态转移方程：
上面的状态转移方程表示，当str[i]=str[j]时，如果str[i+1...j-1]是回文串，则str[i...j]也是回文串；如果str[i+1...j-1]不是回文串，则str[i...j]不是回文串。
初始状态：dp[i][i]=1（单核）dp[i][i+1]=1 if str[i]==str[i+1]（双核）
时间复杂度：O(n^2)
#include<iostream>
#include<vector>
using namespace std;
string longestPalindrome(string s)
{
if (s.empty()) return "";
int len = s.size();
if (len == 1)return s;
int longest = 1;
int start=0;
vector<vector<int> > dp(len,vector<int>(len));
for (int i = 0; i < len; i++)
{
dp[i][i] = 1;
if(i<len-1)
{
if (s[i] == s[i + 1])
{
dp[i][i + 1] = 1;
start=i;
longest=2;
}
}
}
for (int l = 3; l <= len; l++)//子串长度
{
for (int i = 0; i+l-1 < len; i++)//枚举子串的起始点
{
int j=l+i-1;//终点
if (s[i] == s[j] && dp[i+1][j-1]==1)
{
dp[i][j] = 1;
start=i;
longest = l;
}
}
}
return s.substr(start,longest);
}
int main(){
string s;
cin>>s;
string sub=longestPalindrome(s);
cout<<sub;
return 0;
}方法（四）Manacher法
这是一个专门用作处理最长回文子串的方法，这里直接借用了别人的讲解方法。其实主要思想是，把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串，这个叫中心扩展法，但是这个方法还要考虑到处理abba这种偶数个字符的回文串。Manacher法将所有的字符串全部变成奇数个字符。
时间复杂度为：O(n)
#include<iostream>
#include<vector>
using namespace std;
string longestPalindrome(string s)
{
string manaStr = "$#";
for (int i=0;i<s.size();i++) //首先构造出新的字符串
{
manaStr += s[i];
manaStr += '#';
}
vector<int> rd(manaStr.size(), 0);//用一个辅助数组来记录最大的回文串长度，注意这里记录的是新串的长度，原串的长度要减去1
int pos = 0, mx = 0;
int start = 0, maxLen = 0;
for (int i = 1; i < manaStr.size(); i++)
{
rd[i] = i < mx ? min(rd[2 * pos - i], mx - i) : 1;
while (i+rd[i]<manaStr.size() && i-rd[i]>0 && manaStr[i + rd[i]] == manaStr[i - rd[i]])//这里要注意数组越界的判断，源代码没有注意，release下没有报错
rd[i]++;
if (i + rd[i] > mx) //如果新计算的最右侧端点大于mx,则更新pos和mx
{
pos = i;
mx = i + rd[i];
}
if (rd[i] - 1 > maxLen)
{
start = (i - rd[i]) / 2;
maxLen = rd[i] - 1;
}
}
return s.substr(start, maxLen);
}
int main(){
string s;
cin>>s;
string sub=longestPalindrome(s);
cout<<sub;
return 0;
}
京公网安备 11010502036488号