hdu 3068
求一個(gè)字符串的最長回文長度。
套用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;
}
