- 题目描述:
-
回文串就是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。
回文子串,顾名思义,即字符串中满足回文性质的子串。
给出一个只由小写英文字符a,b,c...x,y,z组成的字符串,请输出其中最长的回文子串的长度。
- 输入:
-
输入包含多个测试用例,每组测试用例输入一行由小写英文字符a,b,c...x,y,z组成的字符串,字符串的长度不大于200000。
- 输出:
-
对于每组测试用例,输出一个整数,表示该组测试用例的字符串中所包含的的最长回文子串的长度。
- 样例输入:
-
abab bbbb abba
- 样例输出:
-
3 4 4
-
#include <stdio.h> char s[200002]; char str[400010]; int p[400010]; int min(int a,int b){ return a < b ? a : b; } int pre(){ int i,j = 0; str[j++] = '$'; for(i = 0;s[i];i++){ str[j++] = '#'; str[j++] = s[i]; } str[j++] = '#'; str[j] = '\0'; return j; } void manacher(int n){ int mx = 0,id,i; p[0] = 0; for(i = 1;i < n;i++){ if(mx > i) p[i] = min(mx - i,p[2 * id - i]); else p[i] = 1; while(str[i - p[i]] == str[i + p[i]]) p[i]++; if(p[i] + i > mx){ mx = p[i] + i; id = i; } } } int main(int argc, char const *argv[]){ while(scanf("%s",s) != EOF){ int n = pre(); manacher(n); int ans = 0,i; for(i = 1;i < n;i++) if(p[i] > ans) ans = p[i]; printf("%d\n",ans - 1); } return 0; }