2795: [Poi2012]A Horrible Poem

Time Limit: 50 Sec  Memory Limit: 128 MB

Submit: 640  Solved: 322

[][][]

Description

给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。

如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。

Input

 

第一行一个正整数n (n<=500,000)，表示S的长度。

第二行n个小写英文字母，表示字符串S。

第三行一个正整数q (q<=2,000,000)，表示询问个数。

下面q行每行两个正整数a,b (1<=a<=b<=n)，表示询问字符串S[a..b]的最短循环节长度。

 

Output

依次输出q行正整数，第i行的正整数对应第i个询问的答案。

 

Sample Input

8

aaabcabc

3

1 3

3 8

4 8

Sample Output

1

3

5

 %%https://blog.csdn.net/ww140142/article/details/48260615

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 8 #define G 29 9 #define N 50000710 #define mod 100000000711 #define ll long long12 13 #define Wb putchar(' ')14 #define We putchar('\n')15 #define rg register int16 using namespace std;17 inline int read()18 {19 int x=0,f=1;char ch=getchar();20 while(!isdigit(ch)){ if(ch=='-')f=-1;ch=getchar();}21 while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}22 return x*f;23 }24 inline void write(int x)25 {26 if(x<0) putchar('-'),x=-x;27 if (x==0) putchar(48);28 int num=0;char c[15];29 while(x) c[++num]=(x%10)+48,x/=10;30 while(num) putchar(c[num--]);31 }32 33 int n,Q;34 char ch[N];35 ll bin[N],hash[N];36 bool flag[N];37 vector
           
            ve[N];38 39 void init_prime()40 {41 for (rg i=2;i<=n;i++)42 if (!flag[i])43 {44 rg x=i;45 while(x<=n)46 {47 int z=x;48 while(z%i==0) ve[x].push_back(i),z/=i;49 flag[x]=true;50 x+=i;51 }52 }53 }54 bool judge(int x,int l,int r)55 {56 ll res1=hash[r-x]-(hash[l-1]*bin[(r-x)-l+1])%mod;57 ll res2=hash[r]-(hash[l+x-1]*bin[(r-x)-l+1])%mod;58 res1=(res1%mod+mod)%mod,res2=(res2%mod+mod)%mod;59 return res1==res2;60 }61 int main()62 {63 n=read(),scanf("%s",ch+1),bin[0]=1,init_prime();64 for (int i=1;i<=n;i++)65 hash[i]=(hash[i-1]*G+ch[i]-'a')%mod,bin[i]=(bin[i-1]*G)%mod;66 Q=read();67 while(Q--)68 {69 int l=read(),r=read(),num=r-l+1,ans=num;70 if (num==1) write(1),We;71 else 72 {73 for (rg i=0;i