HOJ 3068 最长回文（manacher回文串，裸题）

manacher回文串，裸题
本题要点：
1、manacher算法，相对较容易理解。假如字符串的长度是 n，
该方法可以在 O(n)的时间内，求出最长的回文串的长度和具体的回文串
2、此题很裸。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxL = 120005;
char s[MaxL], ms[MaxL * 2];
int RL[MaxL * 2];int main()
{
    while(scanf("%s", s) != EOF){
    int len = strlen(s);len = len * 2 + 1;for(int i = 0; i < len; ++i){
    if(i % 2 == 0){
    ms[i] = '#';}else{
    ms[i] = s[(i - 1) / 2];}}int maxRight = 0, pos = 0, maxLen = 0;for(int i = 0; i < len; ++i){
    if(i < maxRight){
    RL[i] = min(RL[2 * pos - i], maxRight - i);}else{
    RL[i] = 1;}while(i - RL[i] >= 0 && i + RL[i] < len && ms[i - RL[i]] == ms[i + RL[i]]){
    ++RL[i];}if(RL[i] + i - 1 > maxRight){
    maxRight = RL[i] + i - 1;pos = i;}maxLen = max(maxLen, RL[i]);}printf("%d\n", maxLen - 1);	}return 0;
}/* aaaaabab *//* 4 3 */