字符串哈希+质因数分解

Luogu P3538

题意

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

题解

初看此题，感觉与 UVA10298 Power Strings 十分相似（但那题数据水啊，字符串hash+暴力即可），此题询问过百万肯定TLE。
考虑优化，首先一个很显然的命题： 判断区间[l,r][l,r]构成循环节长度为lenlen的循环只要判断hash[l,r−len]=hash[l+len,r]hash[l,r-len]=hash[l+len,r]即可。这个证明很简单，不再赘述。
继续优化，可以发现循环节的个数是串长与串内每个字符个数的因数。也就是说要求出串长与串内每个字符个数的最大公约数gg，再枚举gg的因子，每次O(∣s∣),∣s∣O(\sqrt{|s|}),|s|为询问的串长。如果数据够水应该是能过的，但我们还有更优的做法。
假设我们已经证明循环节的长度可为lenlen，就可以把原询问缩小，求当前长度为lenlen的字符串的最短循环节。这实际上就是在做质因数分解，枚举质因数pip_i，若使len/pilen/p_i成为可行的循环节长度，就更新ans=len/pians=len/p_i。考虑到线性筛素数时每一个数背其最小的质因数筛到，记录一些v[i]v[i]表示ii最小的质因数方便分解质因数。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
typedef unsigned long long ull;
using namespace std;
const int N = 500010;
const ull d = 27ull;
char s[N];
ull hsh[N],pw[N]={1ull};
int n,p[N],v[N],tot,q;
void init() {
    for(int i=1;i<=n;i++) {
        pw[i]=pw[i-1]*d;
    }
    for(int i=1;i<=n;i++){
        hsh[i]=hsh[i-1]*d+(ull)(s[i]-'a'+1);
    }
}
void initp(int n) {
    for(int i=2;i<=n;i++) {
        if (!v[i]) p[tot++]=i,v[i]=i;
        for(int j=0;j<tot;j++) {
            if (i*p[j]>n) break; 
            v[i*p[j]]=p[j]; //p[j]是i * p[j]的最小素因子
            if (i%p[j]==0) {
                break;
            }
        }
    }
}
ull gethash(int l,int r){
    return hsh[r]-hsh[l-1]*pw[r-l+1];
}
int main(){
    scanf("%d%s",&n,s+1);
    init();initp(n);
    scanf("%d",&q);
    while(q--) {
        int l,r;
        scanf("%d%d",&l,&r);
        int len=r-l+1,p=v[len],pp=len;
        while(p) {
            int k=pp/p; // k 循环节长度
            if(gethash(l,r-k)==gethash(l+k,r))
                pp=k;
            len/=p;
            p=v[len];
        }
        if(gethash(l,r-1)==gethash(l+1,r)) pp=1;
        printf("%d\n",pp);
    }
}