【BZOJ2803】[Poi2012]Prefixuffix

对于两个串S1、S2，如果能够将S1的一个后缀移动到开头后变成S2，就称S1和S2循环相同。例如串ababba和串abbaab是循环相同的。
给出一个长度为n的串S，求满足下面条件的最大的L：
1. L<=n/2
2. S的L前缀和S的L后缀是循环相同的。

第一行一个正整数n (n<=1,000,000)。第二行n个小写英文字母，表示串S。

一个整数，表示最大的L。

#include <cstdio>#include <cstring>#include <iostream>using namespace std;typedef long long ll;const int maxn=1000010;const ll mod=1000000009;ll seed[maxn],s[maxn],hash[maxn];int n,ans;char str[maxn];ll gethash(int a,int b){	return (hash[b]-hash[a-1]*seed[b-a+1]%mod+mod)%mod;}int main(){	seed[1]=1000000007,seed[0]=1;	scanf("%d%s",&n,str+1);	int i,j;	for(i=1;i<=n;i++)		seed[i]=seed[i-1]*seed[1]%mod,s[i]=(s[i-1]+str[i])%mod,hash[i]=(hash[i-1]*seed[1]+str[i])%mod;	for(i=n/2,j=0;i>0;i--,j=min(j+2,n/2-i))	{		if(s[i]==s[n]-s[n-i]&&gethash(1,i)==gethash(n-i+1,n))		for(;j>=0;j--)		{			if(s[i+j]-s[i]==s[n-i]-s[n-i-j]&&gethash(i+1,i+j)==gethash(n-i-j+1,n-i))			{				ans=max(ans,i+j);				break;			}		}	}	printf("%d",ans);	return 0;}