题意：给一个字符串s，求最长回文串的长度。
思路：manacher算法模板题，点击入门。
Code(板子)：
#include <algorithm>
#include <string.h>
#include <cstdio>
using namespace std;
const int maxn = 110005;
char s[maxn*2];
int p[maxn*2];
int manacher()
{
memset(p, 0, sizeof p);
int id, maxlen, len = strlen(s);
for(int i = len; i >= 0; --i)
{
s[i*2+2] = s[i];
s[i*2+1] = '#';
}
s[0] = '$';
id = 0, maxlen = 1;
for(int i = 1; i <= 2*len+1; ++i)
{
if(id+p[id] > i) p[i] = min(p[id-(i-id)], id+p[id]-i);
else p[i] = 1;
while(s[i-p[i]] == s[i+p[i]]) ++p[i];
if(id+p[id] < i+p[i]) id = i;
if(maxlen < p[i]) maxlen = p[id];
}
return maxlen-1;
}
int main()
{
while(~scanf("%s", s)) printf("%d\n", manacher());
return 0;
}
继续加油~
