BZOJ2795 [Poi2012]A Horrible Poem

首先答案答案一定是长度的约数并且把询问串开头去掉答案那么长结尾去掉答案那么长得到的两个串是相等的

判相等可以用hash

但是直接枚举会T

我们发现循环节重复的次数一定是每个字母出现次数的约数，所以求出所有字母出现次数还有区间长度的最大公约数，枚举这个约数，然后就过了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<queue>
#include<stack>
using namespace std;
#define MAXN 500010
#define MAXM 1010
#define INF 1000000000
#define MOD 1000000007
#define eps 1e-8
#define ll long long
ll bas=233;
int n,m;
char s[MAXN];
ll h[MAXN];
ll mi[MAXN];
int S[MAXN][26];
int gcd(int x,int y){
	return !y?x:gcd(y,x%y);
}
ll hs(int x,int y){
	return (h[x+y-1]-h[x-1]*mi[y]%MOD+MOD)%MOD;
}
bool jud(int x,int y,int l){
	return hs(x,y-x+1-l)==hs(x+l,y-x+1-l);
}
int main(){
	/*
	freopen("okr8.in","r",stdin);
	freopen("dui.txt","w",stdout);
	//*/
	int i,j,x,y;
	scanf("%d%s",&n,s+1);
	mi[0]=1;
	for(i=1;i<=n;i++){
		mi[i]=mi[i-1]*bas%MOD;
		h[i]=(h[i-1]*bas+s[i])%MOD;
		for(j=0;j<26;j++){
			S[i][j]=S[i-1][j]+((s[i]-'a')==j);
		}
	}
	scanf("%d",&m);
	while(m--){
		scanf("%d%d",&x,&y);
		int c=y-x+1;
		for(i=0;i<26;i++){
			c=gcd(c,S[y][i]-S[x-1][i]);
		}
		if(c==1){
			printf("%d\n",y-x+1);
			continue ;
		}
		bool flag=0;
		for(i=1;i*i<=c;i++){
			if(!(c%i)){
				if(jud(x,y,(y-x+1)/c*i)){
					printf("%d\n",(y-x+1)/c*i);
					flag=1;
					break;
				}
			}
		}
		if(flag){
			continue ;
		}
		
		
		for(i--;i;i--){
			if(!(c%i)){
				if(jud(x,y,(y-x+1)/i)){
					printf("%d\n",(y-x+1)/i);
					break;
				}
			}
		}
	}
	return 0;
}

/*

*/