POI2012 PRE-Prefixuffix

P3546 [POI2012] PRE-Prefixuffix

题目大意

对于两个字符串$S_1,S_2$，如果将$S_1$的一个后缀移动到开头后这个字符串变成了$S_2$，则称$S_1,S_2$循环同构。

给定一个长度为$n$的字符串$S$，求满足下面条件的最大的$L$：

• $L$不超过$\frac{n}{2}$
• $S$长度为$L$的前缀和$S$长度为$L$的后缀循环等价

$1\le n\le 10^6$

题解

题目要求的就是形如下面这样的前后缀，其中红色部分相同，绿色部分相同。

判断两个字符串相同可以用哈希。对于每个位置$i$，我们用$f_i$表示满足以下条件的的最大的$k$：

• $[i,i+k?1]=[n?i?k+2,n?i+1]$
• $i+k?1\le \frac{n}{2}$

如果通过枚举$k$来求每个$f_i$的话，时间复杂度是$O(n^2)$的，我们考虑优化。

我们发现，$f_{i?1}\le f_i+2$，证明如下：

假设$f_{i?1}>f_i+2$，因为$f_{i?1}$比$f_i$多了$i?1$这个位置，如果将$f_{i?1}$对应的绿色部分的第一个字符和最后一个字符去掉，那么一定符合$f_i$的条件，也就是说$f_i$至少为$f_{i?1}?2$，推得$f_{i?1}\le f_i+2$，与$f_{i?1}>f_i+2$矛盾，得证$f_{i?1}\le f_i+2$。

根据这个条件，我们可以$O(n)$求出所有$f_i$。

然后，对于每个$i$，判断$[1,i]$和$[n?i+1,n]$是否相同，如果相同就用$i+f_i?1$更新答案。

时间复杂度为$O(n)$。

code

#include<bits/stdc++.h>
using namespace std;
const int base=233;
const long long mod=1e9+7;
const int N=1000000;
int n,ans=0,f[N+5];
long long pw[N+5],g[N+5];
char s[N+5];
long long gt(int l,int r){
	return (g[r]-g[l-1]*pw[r-l+1]%mod+mod)%mod;
}
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	pw[0]=1;
	for(int i=1;i<=n;i++){
		g[i]=(g[i-1]*base+s[i]-'a'+1)%mod;
		pw[i]=pw[i-1]*base%mod;
	}
	for(int i=n/2;i>=1;i--){
		f[i]=min(f[i+1]+2,n/2-i+1);
		while(f[i]>0&&gt(i,i+f[i]-1)!=gt(n-i-f[i]+2,n-i+1)) --f[i];
	}
	for(int i=1;i<=n/2;i++){
		if(gt(1,i-1)==gt(n-i+2,n)) ans=max(ans,i+f[i]-1);
	}
	printf("%d",ans);
	return 0;
}