LeetCode 5 Longest Palindromic Substring manacher算法,最长回文子序列,string.substr(start,len) 难度:2

时间:2024-09-12 19:03:20

https://leetcode.com/problems/longest-palindromic-substring/

manacher算法相关:http://blog.****.net/ywhorizen/article/details/6629268

class Solution {
public: string longestPalindrome(string s)
{
char ch[2001];int p[2001];
ch[2*s.size()] = 0;
for(int i = 0; i < 2 * s.size(); i++)
{
if((i & 1) == 1)ch[i] = s[(i>>1)];
else ch[i] = ' ';
}
int mx = 1,id = 0;
p[0] = 1;
int ss = 0,se = 0;
for(int i = 1; ch[i]; i++)
{
if(mx <= i)
{
p[i] = 1;
}
else
{
p[i] = min(p[id * 2 - i],mx - i);
}
while(ch[i + p[i]] == ch[i - p[i]] && i >= p[i])
{
p[i]++;
}
if(p[i] + i > mx)
{
id = i;
mx = p[i] + i;
}
int ts = (i - p[i] + 1)/2;
int te = (i + p[i] - 2)/2;
if(te - ts >se - ss){
se = te;ss = ts;
}
}
return s.substr(ss,se -ss + 1);
}
};