给出一个由小写英文字母组成的字符串S,再给出q个询问,要求回答S某个子串的最短循环节。
如果字符串B是字符串A的循环节,那么A可以由B重复若干次得到。
BZOJ2795: [Poi2012]A Horrible Poem
给出一个由小写英文字母组成的字符串S,再给出q个询问,要求回答S某个子串的最短循环节。
如果字符串B是字符串A的循环节,那么A可以由B重复若干次得到。
第一行一个正整数n (n<=500,000),表示S的长度。
第二行n个小写英文字母,表示字符串S。
第三行一个正整数q (q<=2,000,000),表示询问个数。
下面q行每行两个正整数a,b (1<=a<=b<=n),表示询问字符串S[a..b]的最短循环节长度。
依次输出q行正整数,第i行的正整数对应第i个询问的答案。
所以我们可以在求出这个区间的长度之后,判断它的每个约数是否是循环节(应用性质3),并且因为性质1,它的约数是循环节,原串一定也是。
所以只要不断除以质因数(相当于从大到小枚举约数),缩小$L$的长度,最后就是最小的长度。
而一个重要的点在于,用上面方法来枚举约数是为了避免$TLE$。
在求它的质因数的时候,可以通过线性筛的过程求得,将时间复杂度由$O(\sqrt n)$降为$O(\log_2n)$。
所以总复杂度就是$O(n\log_2n)$。
注意这里枚举到全长。
附代码:
#include<iostream> #include<algorithm> #include<cstdio> #define MAXN 500010 #define MOD 29 using namespace std; int n,m; int val[MAXN],hash[MAXN]; char str[MAXN]; int k=0,prime[MAXN],min_prime[MAXN]; bool np[MAXN]; inline int read(){ int date=0,w=1;char c=0; while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();} return date*w; } void make(){ int m=MAXN-10; for(int i=2;i<=m;i++){ if(!np[i]){ prime[++k]=i; min_prime[i]=i; } for(int j=1;j<=k&&prime[j]*i<=m;j++){ np[prime[j]*i]=true; min_prime[prime[j]*i]=prime[j]; if(i%prime[j]==0)break; } } val[0]=1; for(int i=1;i<=n;i++){ val[i]=val[i-1]*MOD; hash[i]=hash[i-1]*MOD+(str[i]-‘0‘+1); } } inline bool check(int l1,int r1,int l2,int r2){ int x=hash[r1]-hash[l1-1]*val[r1-l1+1],y=hash[r2]-hash[l2-1]*val[r2-l2+1]; return (x==y); } void work(){ int x,y; while(m--){ x=read();y=read(); int ans=y-x+1; for(int j=y-x+1;j>1;){ int k=min_prime[j]; while(ans%k==0&&check(x,y-ans/k,x+ans/k,y))ans/=k; while(j%k==0)j/=k; } printf("%d\n",ans); } } void init(){ n=read(); scanf("%s",str+1); make(); m=read(); } int main(){ init(); work(); return 0; }
BZOJ2795: [Poi2012]A Horrible Poem
原文:https://www.cnblogs.com/Yangrui-Blog/p/9515235.html