HDU - 3068（manacher 求回文）_综合

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等

Input

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000

Output

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

Sample Input

aaaaabab

Sample Output

4
3

思路：套了manacher的模板，感觉比KMP简单一些。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx = 110000 + 10;
char s1[mx], str[2 * mx];
int len[2 * mx];
int manacher(){str[0] = '@';int n = strlen(s1), cnt =0;for(int i = 0; i < n; i++){str[++cnt] = '#';str[++cnt] = s1[i];}str[++cnt] = '#';str[++cnt] = 0;int rmx = 0, mid = 0, ans = 1;for(int i = 1; i < cnt; i++){if(i <rmx)len[i] = min(rmx - i, len[2 * mid - i]);elselen[i] = 1;while(str[i + len[i]] == str[i - len[i]])len[i]++;if(i + len[i] > rmx){rmx = i + len[i];mid = i;}ans = max(len[i], ans);}return ans - 1;
}
int main(){while(scanf("%s", s1) != EOF){printf("%d\n", manacher());}return  0;}