解析详见：http://blog.sina.com.cn/s/blog_7cfbb10f010170rt.html
#include#include #include using namespace std; #define N 225000 //dp[i] 表示以i点为中心向右最大回文长度 //则答案就是max(dp[i]) -1 int dp[N]; char P[N], T[N]; //在每一个字符间插入# 这样得到的回文串长度一定是奇数（包含#) int Have_P(){ int j, len = strlen(T); j = 0; P[j++] = '$'; P[j++] = '#'; for(int i = 0; i < len; i++) P[j++] = T[i], P[j++] = '#'; P[j] = '\0'; return j; } void KMP(int Plen){ int mx = 0, id = 0; dp[0] = 0; for(int i = 1; i < Plen; i++) { dp[i] = mx>i min(dp[2*id-i], mx-i) : 1; while(P[i + dp[i]] == P[i - dp[i]])dp[i]++; if(i + dp[i] > mx) { mx = dp[i] + i; id = i; } } } int main(){ while(~scanf("%s", T)){ int len, ans = 0; KMP(len = Have_P()); for(int i = 0; i < len; i++) ans = max(ans, dp[i]-1); printf("%d\n",ans); } return 0; }