A Horrible Poem

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1671 字
哈希加质因数分解求子串最短循环节
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1460
// 题意：给长 n 的串 S 与 q 个询问 [a,b]，输出子串 S[a..b] 的最短循环节长度。
// 思路：预处理滚动哈希 O(1) 判两段相等；对每个询问把长度质因数分解，从 ans=len 起对每个质因子尝试除下去并用哈希验证周期性。
// 复杂度：O(n+q·log n) 时间 / O(n) 空间
// 易错点：判周期是比较 S[l..r-d] 与 S[l+d..r] 两段，d 必须严格小于子串长度；q 达 2e6 必须关同步并直接输出。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull BS=911382323ull;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin>>n)) return 0;
    string s;
    if(!(cin>>s)) return 0;
    vector<ull> h(n+1,0),pw(n+1,1);
    for(int i=0;i<n;i++){
        h[i+1]=h[i]*BS+(ull)(unsigned char)s[i];
        pw[i+1]=pw[i]*BS;
    }
    auto seg=[&](int l,int r)->ull{
        if(l>r) return 0ull;
        return h[r+1]-h[l]*pw[r-l+1];
    };
    int lim=(int)sqrt((double)n)+2;
    vector<int> primes;
    vector<int> comp(lim+1,0);
    for(int i=2;i<=lim;i++){
        if(!comp[i]) primes.push_back(i);
        for(int p:primes){
            long long v=1LL*i*p;
            if(v>lim) break;
            comp[(int)v]=1;
            if(i%p==0) break;
        }
    }
    int q;
    if(!(cin>>q)) return 0;
    while(q--){
        int a,b;
        cin>>a>>b;
        int l=a-1,r=b-1;
        int len=r-l+1;
        int ans=len;
        int x=len;
        for(int p:primes){
            if(1LL*p*p>x) break;
            if(x%p==0){
                while(x%p==0){
                    if(ans%p==0&&seg(l,r-ans/p)==seg(l+ans/p,r)) ans/=p;
                    x/=p;
                }
            }
        }
        if(x>1){
            if(ans%x==0&&seg(l,r-ans/x)==seg(l+ans/x,r)) ans/=x;
        }
        cout<<ans<<'\n';
    }
    return 0;
}
A Horrible Poem

正文

一本通·提高篇的其它内容
