题面
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba, abba等
输入
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S 两组case之间由空行隔开(该空行不用处理) 字符串长度len <= 110000
输出
每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
样例输入
样例输出
提示
无
思路
Manacher模板题。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| char s[mxn], t[mxn]; int p[mxn];
int manacher_init(char *s, char *t, int n) { int j = 2; t[0] = '$', t[1] = '#'; for (int i=0; i<n; i++) { t[j++] = s[i]; t[j++] = '#'; } t[j] = '\0'; return j; }
int manacher(char *t, int *p, int n) { int id = 0, mx = 0, ans = 0; for (int i=1; i<=n; i++) { p[i] = i<mx ? min(p[2*id-i], mx-i) : 1;
while (t[i+p[i]] == t[i-p[i]]) p[i]++;
if (mx < i+p[i]) mx = i+p[i], id = i;
ans = max(ans, p[i]); } return ans-1; }
int main() { while(~scanf("%s", s)) { int n = manacher_init(s, t, strlen(s)); printf("%d\n", manacher(t, p, n)); }
return 0; }
|