BZOJ2795&2890&3647[Poi2012]A Horrible Poem—

BZOJ2795&2890&3647[Poi2012]A Horrible Poem——hash

阅读量：5863 次

发布时间：2019-06-19

本文共 2119 字，大约阅读时间需要 7 分钟。

题目描述

给出一个由小写英文字母组成的字符串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个询问的答案。

样例输入

aaabcabc

1 3

3 8

4 8

样例输出

对于一个串的循环节有几个性质，这些性质也是解题的关键所在：

1、如果B串是A串的循环节，那么B串长度一定是A串长度的约数。

2、如果B串是A串的循环节，设A串区间为[l,r]，B串长度为x，[l+x,r]和[l,r-x]一定相同(判断循环节的关键所在)，这个很好证明，因为A串由几个B拼接而成，从前面拿掉一个B和从后面拿掉一个B，剩下串自然是一样的。

3、如果B串是A串的最短循环节，那么所有A串循环节的长度都是B串长度的倍数，也就是说不是B串长度倍数的一定不是循环节。举个例子：假如A串长度为6(每个字符分别用s1,s2,s3,s4,s5,s6表示)，最短循环节长度为2，长度为3的子串一定不是循环节，因为s1=s3=s5,s2=s4=s6且s1≠s2即s1≠s4,但如果长度为3的是循环节，s1=s4，显然矛盾，由此推广就能证明上述结论。

因为一个A串的长度由几个质因子相乘得到，所以只要判断长度除掉某个质因子之后得到的子串是否为循环节，如果是，就说明这个串中是最短循环节的倍数。这里用线性筛法筛质因子，在线性筛素数时记录每个数的最小质因子，每个查询是枚举质因子O(1)判断。

这三道题中有一道卡自然溢出。

最后附上代码。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            using namespace std;unsigned long long h[500010];long long g[500010];long long m[500010];unsigned long long k[500010];const int base=13131;long long mod=2333333333ll;int vis[500010];int prime[100010];int s[500010];char ch[500010];int n,q;int l,r;int ans;int len;int cnt;void find(int n){ for(int i=2;i<=n;i++) { if(!vis[i]) { prime[++cnt]=i; s[i]=i; } for(int j=1;j<=cnt&&prime[j]*i<=n;j++) { vis[i*prime[j]]=1; s[i*prime[j]]=prime[j]; if(i%prime[j]==0) { break; } } }}bool check(int l,int r,int L,int R){ if((h[r]-h[l-1]*k[r-l+1]==h[R]-h[L-1]*k[R-L+1])&&(((((g[r]-g[l-1]*m[r-l+1]%mod)%mod)+mod)%mod)==((((g[R]-g[L-1]*m[R-L+1]%mod)%mod)+mod)%mod))) { return true; } return false;}int main(){ scanf("%d",&n); scanf("%s",ch+1); find(n); m[0]=1; k[0]=1; for(int i=1;i<=n;i++) { h[i]=h[i-1]*base+ch[i]; k[i]=k[i-1]*base; g[i]=(g[i-1]*base%mod+ch[i])%mod; m[i]=m[i-1]*base%mod; } scanf("%d",&q); while(q--) { scanf("%d%d",&l,&r); len=r-l+1; ans=len; for(int i=len;i>1;i/=s[i]) { int num=ans/s[i]; if(check(l,r-num,l+num,r)) { ans=num; } } printf("%d\n",ans); }}

转载于:https://www.cnblogs.com/Khada-Jhin/p/9265288.html

你可能感兴趣的文章