hdu 3068 Manacher

hdu 3068
求一个字符串的最长回文长度。
套用Manacher模板即可。

// hdu 3068
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
using namespace std;

#define bll long long
#define dou double
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; ++i)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; --i)
#define Mem(a,b) memset(a,b,sizeof(a))
#define Cpy(a,b) memcpy(a,b,sizeof(b))

const int maxn=110000*2+100;
int P[maxn];
char s[maxn],str[maxn];

void Manacher(char s[],char str[],int P[])
{
    int n=strlen(s+1);
    int len=n<<1|1;
    str[0]='$';
    str[1]='#';
    for (int i=1; i<=n; ++i)
    {
        str[i<<1]=s[i];
        str[i<<1|1]='#';
    }
    str[len+1]=0;
    P[1]=1;
    int mid=1,ri=mid+P[mid];
    for (int i=2; i<=len; ++i)
    {
        int j=(i<ri ? min(ri-i,P[mid-(i-mid)]) : 1);
        while(str[i-j]==str[i+j]) ++j;
        P[i]=j;
        if (i+P[i]>ri)
        {
            mid=i;
            ri=mid+P[mid];
        }
    }
}

int main()
{
    for (; scanf("%s",s+1)!=EOF; )
    {
        Manacher(s,str,P);
        int ans=0;
        int len=strlen(s+1)<<1|1;
        for (int i=1; i<=len; ++i)
            ans=max(ans,P[i]-1);
        printf("%d\n",ans);
    }
    return 0;
}