[BZOJ2795][Poi2012]A Horrible Poem

2021-10-02 22:07:15

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+q\sqrt n)$

 #include<cstdio>

 #include<algorithm>

 #define N 500050

 #define ll unsigned long long

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 ll pow[N]={},hash[N];

 int n,num[N][],q,st[N],top;

 char s[N];

 inline ll gethash(int l,int r)

 {return hash[r]-hash[l-]*pow[r-l+];}

 inline bool check(int l,int r,int x)

 {return gethash(l+x,r)==gethash(l,r-x);}

 inline int gcd(int a,int b){return b?gcd(b,a%b):a;}

 inline int query(int l,int r)

 {

     swap(l,r);

     int x=r-l+,y=r-l+;

     for(int i=;i<=;i++)

     x=gcd(x,num[r][i]-num[l-][i]);

     if(x==)return y;

     top=;

     for(int i=;i*i<=x;i++)

     if(!(x%i))

     {

         st[++top]=y/i;

         if(check(l,r,y/x*i))

         return y/x*i;

     }

     while(!check(l,r,st[top]))top--;

     return st[top];

 }

 int main()

 {

     scanf("%d\n",&n);

     gets(s+);

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

     hash[i]=hash[i-]*+s[i],

     pow[i]=pow[i-]*;

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

     for(int j=;j<=;j++)

     num[i][j]=num[i-][j]+(s[i]-'a'+==j);

     q=read();

     while(q--)printf("%d\n",query(read(),read()));

 }

码农公寓