题意:
给你一个字符串,长度 n <= 106 。求这个字符串的最长连续回文子串的长度。
解法:
Manacher算法可以在O(n) 的时间内求得一个字符串的最长连续回文子串,属于模板题。
算法详解:http://www.cnblogs.com/biyeymyhjob/archive/2012/10/04/2711527.html。
代码:
#include <iostream> #include <string> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int maxn = 1e6+5; int p[maxn << 1]; char str[maxn]; char a[maxn << 1]; int main(){ int cc = 1; while(~scanf("%s",str), strcmp(str,"END")!=0) { memset(p,0,sizeof(p)); int d = 0; a[d ++] = '$'; a[d ++] = '#'; for(int i = 0 ; str[i] ; i++){ a[d++] = str[i]; a[d++] = '#'; } a[d] = '\0'; int mx = 0 , id = 0; for(int i = 1 ; a[i] ; i++) { p[i] = mx>i ? min(p[2*id-i], mx-i) : 1; while(a[i-p[i]] == a[i+p[i]]) p[i] ++; if(i+p[i] > mx) { mx = i+p[i]; id = i; } } int ans = -1; for(int i = 0 ; a[i] ; i++){ ans = max(ans, p[i]); } printf("Case %d: %d\n", cc++, ans-1); } }