Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
求最长回文子串的裸题,搞竞赛的时候遇到过各种花样的变式。
n方的朴素算法已经烂大街了,推荐使用O(n)的算法,只可惜很久没用过manacher算法,不会写了,所以花了一段时间温故知新。
manacher算法原理不了解的道友可以看这篇文章:
https://cloud.tencent.com/developer/article/1019346
class Solution
{
public:
string init(string s)
{
string result("*#");//防止越界
for(int i=0;i<s.length();i++)
{
result+=s[i];
result+='#';
}
result+='&';
return result;
}
string longestPalindrome(string s)
{
string ch=init(s);
int p[2010],id=0,maxlen=0,pos=0;
p[0]=0;
for(int i=1;i<ch.length();i++)
{
if(p[id]+id>i)
p[i]=min(p[2*id-i],p[id]+id-i);
else
p[i]=1;
while(ch[i-p[i]] == ch[i+p[i]])
p[i]++;
if(id+p[id]<i+p[i])
id=i;
if(maxlen<p[i])
{
pos=i;
maxlen=p[i];
}
}
pos/=2;
string result=s.substr(pos-maxlen/2,maxlen-1);
return result;
}
};