# 10038. 「一本通 2.1 练习 4」A Horrible Poem

【题目描述】

给出一个由小写英文字母组成的字符串 $S$，再给出 $q$ 个询问，要求回答 $S$ 某个子串的最短循环节。

如果字符串 $B$ 是字符串 $A$ 的循环节，那么 $A$ 可以由 $B$ 重复若干次得到。

【算法】

-首先对于长度为 $len$ 的子串，循环节长度为 $x$ 的充要条件：$[1，len-x]$串的哈希值等于 $[x+1，len]$ 串的哈希值。

-一开始暴力枚举最短循环节长度（n的约数），然后T了一半。

有两种方法进行优化：

1、循环节个数必然是子串各个字母个数和子串长度的公约数，可以枚举循环节个数此时bzoj就能过了，但是loj还是会T。(93分) $O(q\sqrt{n})$

2、正解：假设最短循环节长度为len则原串长度显然为len*k。若只考虑k，并且将k的质因数依次分解，每次试除k，则得到的$k^。$和len的乘积仍是循环节，利用这个性质。依次用质因数 $i$ 试除n，若除去后仍是循环节，说明i属于k，将其除去，结果就留下了len。

【代码1】

#include <bits/stdc++.h>

#define P 131

#define ULL unsigned long long

using namespace std;

int n,q,a,b,len;

int rec[500010][26];

ULL h[500010],p[500010];

char s[500010];

inline int read() {

    int x=0,f=1; char c=getchar();

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

    while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); }

    return x*f;

}

void parse() {

    p[0]=1;

    for(int i=1;i<=n;i++) p[i]=p[i-1]*P,h[i]=h[i-1]*P+(ULL)s[i];

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

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

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

}

int gcd(int x,int y) {

    return y?gcd(y,x%y):x;

}

bool valid(int l) {

    return h[b]-h[a+l-1]*p[len-l]==h[a+(len/l-1)*l-1]-h[a-1]*p[len-l];

}

int main() {

    n=read();

    gets(s+1);

    q=read();

    parse();

    while(q--) {

        a=read(),b=read();

        len=b-a+1;

        int num=len,ans=0;

        for(int i=1;i<=26;i++) num=gcd(num,rec[b][i]-rec[a-1][i]);

        for(int i=1;i*i<=num;i++) {

            if(num%i==0) {

                if(valid(len/(num/i))) { ans=max(ans,num/i); break; }

                if(valid(len/i)) ans=max(ans,i);

            }

        }

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

    }

    return 0;

}

【ac代码】

#include <bits/stdc++.h>

#define N 500010

#define P 131

#define ULL unsigned long long

using namespace std;

int n,q,len,tot;

ULL h[N],p[N];

int prime[N],minp[N];

char s[N];

inline int read() {

    int x=0,f=1; char c=getchar();

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

    while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); }

    return x*f;

}

void parse() {

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

        if(!minp[i]) {

            prime[++tot]=i;

            minp[i]=i;

        }

        for(int j=1;j<=tot;j++) {

            if(prime[j]>minp[i]||prime[j]*i>n) break;

            minp[prime[j]*i]=prime[j];

        }

    }

    p[0]=1;

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

        h[i]=h[i-1]*P+(ULL)s[i],p[i]=p[i-1]*P;

}

bool valid(int a,int b,int l) {

    return h[b]-h[a+l-1]*p[len-l]==h[a+(len/l-1)*l-1]-h[a-1]*p[len-l];

}

int main() {

    n=read();

    gets(s+1);

    q=read();

    parse();

    while(q--) {

        int a,b,ans,tmp;

        a=read(),b=read();

        len=tmp=ans=b-a+1;

        while(tmp!=1) {

            int t=minp[tmp];

            while(tmp%t==0&&valid(a,b,ans/minp[tmp])) tmp/=t,ans/=t;

            while(tmp%t==0) tmp/=t;

        }

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

    }

    return 0;

}