【BZOJ2795】[Poi2012]A Horrible Poem hash

2022-02-08 00:08:14

【BZOJ2795】[Poi2012]A Horrible Poem

Description

给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。
如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。

Input

第一行一个正整数n (n<=500,000)，表示S的长度。
第二行n个小写英文字母，表示字符串S。
第三行一个正整数q (q<=2,000,000)，表示询问个数。
下面q行每行两个正整数a,b (1<=a<=b<=n)，表示询问字符串S[a..b]的最短循环节长度。

Output

依次输出q行正整数，第i行的正整数对应第i个询问的答案。

Sample Input

8
aaabcabc
3
1 3
3 8
4 8

Sample Output

1
3
5

题解：回忆用KMP求一个单词最短循环节的方法，如果next[n]>=n/2，则最短循环节为n-next[n]。

那么我们就得出了O(1)判断一个长度x是否是给定串的循环节的方法，直接用hash判断s[l...r-x]和s[l+x...r]是否相等即可，那么我们思考这个最短长度是什么。

首先如果x是该串的循环节，则2x，3x也一定是该串的循环节，并且我们已知原串长度len一定是它本身的循环节，那么x一定是len的约数。我们可以将len分解质因数，x的每个质因子的次数一定<=len中每个质因子的次数，从大到小枚举这个次数即可。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const ll m1=998244353;

const ll m2=100000007;

const int maxn=500010;

int n,q,num,ans;

char str[maxn];

int pri[maxn],lp[maxn];

ll b1[maxn],b2[maxn],h1[maxn],h2[maxn];

bool np[maxn];

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

bool check(int a,int b,int c,int d)

{

	return (h1[b]-h1[a-1]*b1[b-a+1]%m1+m1)%m1==(h1[d]-h1[c-1]*b1[d-c+1]%m1+m1)%m1&&(h2[b]-h2[a-1]*b2[b-a+1]%m2+m2)%m2==(h2[d]-h2[c-1]*b2[d-c+1]%m2+m2)%m2;

}

int main()

{

	scanf("%d%s%d",&n,str+1,&q);

	int i,j,a,b,c;

	for(i=2;i<=n;i++)

	{

		if(!lp[i])	pri[++num]=lp[i]=i;

		for(j=1;j<=num&&i*pri[j]<=n;j++)

		{

			lp[i*pri[j]]=pri[j];

			if(i%pri[j]==0)	break;

		}

	}

	for(b1[0]=b2[0]=1,i=1;i<=n;i++)

	{

		h1[i]=(h1[i-1]*233+str[i])%m1,h2[i]=(h2[i-1]*233+str[i])%m2;

		b1[i]=b1[i-1]*233%m1,b2[i]=b2[i-1]*233%m2;

	}

	for(i=1;i<=q;i++)

	{

		a=rd(),b=rd(),c=ans=b-a+1;

		while(c!=1)

		{

			if(check(a,b-ans/lp[c],a+ans/lp[c],b))	ans/=lp[c];

			c/=lp[c];

		}

		printf("%d\n",ans);

	}

	return 0;

}//8 aaabcabc 3 1 3 3 8 4 8

码农公寓