[BZOJ2795][Poi2012]A Horrible Poem

2795: [Poi2012]A Horrible Poem

Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 261 Solved: 150
[Submit][Status][Discuss]

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

HINT

Source

鸣谢 jiangzoi&oimaster

[Submit][Status][Discuss]

hash一下，然后有一个显然的暴力做法，单次询问是$sqrt n$的。

可以优化一下，记录一下每个字母的出现次数，循环节个数一定是这个的约数。

时间复杂度不是很好$O(n+q+qsqrt n)$

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define N 500050
 4 #define ll unsigned long long
 5 using namespace std;
 6 inline int read()
 7 {
 8     int x=0,f=1;char ch=getchar();
 9     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
10     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
11     return x*f;
12 }
13 ll pow[N]={1},hash[N];
14 int n,num[N][30],q,st[N],top;
15 char s[N];
16 inline ll gethash(int l,int r)
17 {return hash[r]-hash[l-1]*pow[r-l+1];}
18 inline bool check(int l,int r,int x)
19 {return gethash(l+x,r)==gethash(l,r-x);}
20 inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
21 inline int query(int l,int r)
22 {
23     swap(l,r);
24     int x=r-l+1,y=r-l+1;
25     for(int i=1;i<=26;i++)
26     x=gcd(x,num[r][i]-num[l-1][i]);
27     if(x==1)return y;
28     top=0;
29     for(int i=1;i*i<=x;i++)
30     if(!(x%i))
31     {
32         st[++top]=y/i;
33         if(check(l,r,y/x*i))
34         return y/x*i;
35     }
36     while(!check(l,r,st[top]))top--;
37     return st[top];
38 }
39 int main()
40 {
41     scanf("%d
",&n);
42     gets(s+1);
43     for(int i=1;i<=n;i++)
44     hash[i]=hash[i-1]*233+s[i],
45     pow[i]=pow[i-1]*233;
46     for(int i=1;i<=n;i++)
47     for(int j=1;j<=26;j++)
48     num[i][j]=num[i-1][j]+(s[i]-'a'+1==j);
49     q=read();
50     while(q--)printf("%d
",query(read(),read()));
51 }

View Code