P3546 [POI2012] PRE-Prefixuffix 做题记录

对于两个字符串 $A,B$，若能将 $A$ 的一个后缀整体移动到 $A$ 的前面则称它们是循环同构的。

给定一个长 $n$ 的字符串，求最大的 $L$ 使得 $S_{[1,L]}$ 和 $S_{[n-L+1,n]}$ 是循环同构的。

$1\le n\le 10^6$。

第一步就没想到。

考虑两个串循环同构当且仅当一个串是 $AB$ 而另一个串是 $BA$，故有 $S=ABCBA$。

那么枚举 $A$ 的长度，然后问题就变成求头尾都去掉 $x$ 个字符后的 border。

设 $f_i$ 表示头尾都去掉 $i$ 个字符后的 border，那么显然有 $f_{i+1}\ge f_i-2$，那么 $i$ 从大往小每次暴力往前跑找到第一个合法即可，实现注意需要双哈希。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int S=1000005;
const int bse=31,p1=1000000007,p2=998244353;

int n;
char a[S];
int pw1[S],pw2[S];
int h1[S],h2[S];

inline int cal1(int l,int r)
{
	return (h1[r]-1ll*pw1[r-l+1]*h1[l-1]%p1+p1)%p1;
}

inline int cal2(int l,int r)
{
	return (h2[r]-1ll*pw2[r-l+1]*h2[l-1]%p2+p2)%p2;
}

inline bool chk(int l,int r,int k)
{
	if(k==0) return true;
	return cal1(l,l+k-1)==cal1(r-k+1,r)&&
		   cal2(l,l+k-1)==cal2(r-k+1,r);
}

int main()
{
	scanf("%d%s",&n,a+1);
	pw1[0]=pw2[0]=1;
	for(int i=1;i<=n;i++)
	{
		pw1[i]=1ll*pw1[i-1]*bse%p1;
		pw2[i]=1ll*pw2[i-1]*bse%p2;
		h1[i]=(1ll*h1[i-1]*bse+a[i]-'a'+1)%p1;
		h2[i]=(1ll*h2[i-1]*bse+a[i]-'a'+1)%p2;
	}
	int ans=0;
	for(int l=n/2,r=n/2+1+(n&1),len=0;l>=1;l--,r++)
	{
		if(chk(1,n,l)) ans=max(ans,l+len);
		if(len+2<=(r-l+1)/2&&chk(l,r,len+2)) len+=2;
		else if(len+1<=(r-l+1)/2&&chk(l,r,len+1)) len++;
		while(!chk(l,r,len)) len--;
	}
	printf("%d\n",ans);
	return 0;
}