P3538 [POI2012]OKR-A Horrible Poem

hash+线性筛

题解 <----这篇写的不错（其实是我懒得码字了qwq）

判断一个长为 u 的子串是否为长为 n 的主串的循环子串只要比较 [1,n-u ]和 [u+1, n]的hash值即可（所以说我以前都是瞎搞〒▽〒）

想了想，还是加点注释吧，不然为啥要写博客总结呢（逃

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cctype>

using namespace std;

typedef unsigned long long ull;

inline int Int(){

    char c=getchar(); int x=;

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

    return x;

}

const int base=;

int n,q,cnt,v[],prime[],it_pri[];

char a[];

ull h1[],fac[]; //自然溢出hash

void get_prime(){ //线性筛筛素数

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

        if(!v[i]) prime[++cnt]=v[i]=i;

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

            if(prime[j]>v[i]||prime[j]>n/i) break;

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

        }

    }

}

inline bool check(int l1,int r1,int l2,int r2){ //hash值比较

    ull p1=h1[r1]-h1[l1-]*fac[r1-l1+];

    ull p2=h1[r2]-h1[l2-]*fac[r2-l2+];

    return p1==p2;

}

int main(){

    n=Int(); scanf("%s",a); fac[]=;

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

        h1[i]=h1[i-]*base+(ull)a[i-];

        fac[i]=fac[i-]*base;

    } //普通的hash

    get_prime();

    q=Int(); int l,r;

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

        l=Int(); r=Int();

        int t=,len=r-l+;

        while(len>) it_pri[++t]=v[len],len/=v[len]; //分解质因数

        len=r-l+;

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

            int u=len/it_pri[j];

            if(check(l,r-u,l+u,r)) len=u; //不断缩小循环子串的最小值

        }

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

    }

    return ;

}

秒客网

P3538 [POI2012]OKR-A Horrible Poem

相关文章