后缀数组 hdu6661 Acesrc and String Theory

男娘i 2021-10-23 15:32 226阅读 0赞

Problem Description

Acesrc is a famous string theorist at Nanjing University second to none. He insists that we should always say an important thing k times. He also believes that every string that can be obtained by concatenating k copies of some nonempty string is splendid. So, he always teaches newcomers, \`\`String theory problems are important! String theory problems are important! ... String theory problems are important!"  
  
Today, he wants to examine whether the newcomers remember his instruction. He presents a string consisting of lower case letters and asks them the number of splendid substrings of the presented string. No one can solve this problem, and they will be scolded for hours. Can you help them solve this problem?  
  
Note that equal splendid substrings occurred in different positions should be counted separately.

Input

The first line of input consists of a single integer T (1≤T≤10), denoting the number of test cases. Each test case starts with a single line of an integer k (1≤k≤20). The second line of a test case is a string S consisting of lower case letters only, the length of which is between 1 and 3×105 inclusive. The sum of the lengths of strings in all test cases never exceeds 106.

Outpu

For each test case, print the answer as a single integer in a single line.

Sample Input

3 2 aabb

2 abababab

3 abc

Sample Output

Source

[2019 Multi-University Training Contest 8][]

这个题和poj3693一样，但是数据没有3693水，所以匹配前后缀以及在划分段的时候，要注意一下。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int M=1e6+50;
    int Log[M],K;
    long long res;
    struct Node{
        int n,m,rk[M],height[M],c[M],sa[M],x[M],y[M],t[M][35];
        char s[M];
        void getsa(){
            for(int i=0;i<=m;i++) c[i]=0;
            for (int i=1; i<=n; ++i) ++c[x[i]=s[i]-'a'+1];
            for (int i=2; i<=m; ++i) c[i]+=c[i-1];
            for (int i=n; i>=1; --i) sa[c[x[i]]--]=i;
            for (int k=1; k<=n; k<<=1) {
                int num=0;
                for (int i=n-k+1; i<=n; ++i) y[++num]=i;
                for (int i=1; i<=n; ++i) if (sa[i]>k) y[++num]=sa[i]-k;
                for (int i=1; i<=m; ++i) c[i]=0;
                for (int i=1; i<=n; ++i) ++c[x[i]];
                for (int i=2; i<=m; ++i) c[i]+=c[i-1];
                for (int i=n; i>=1; --i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
                swap(x,y);
                x[sa[1]]=1;
                num=1;
                for (int i=2; i<=n; ++i)
                    if((y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]))x[sa[i]]=num;
                    else x[sa[i]]=++num;
                if (num==n) break;
                m=num;
            }
            int k=0;
            for (int i=1; i<=n; ++i) rk[sa[i]]=i;
            for (int i=1; i<=n; ++i) {
                if (rk[i]==1) continue;//第一名height为0
                if (k) --k;//h[i]>=h[i-1]-1;
                int j=sa[rk[i]-1];
                while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;
                height[rk[i]]=k;
            }
        }
        void rmq(){
            for(int i=1;i<=n;i++)t[i][0]=height[i];
            for(int j=1;(1<<j)<=n;j++)
                for(int i=1;i+(1<<j)-1<=n;i++)
                    t[i][j]=min(t[i][j-1],t[i+(1<<(j-1))][j-1]);
        }
        int ask(int l,int r){
            l=rk[l],r=rk[r];
            if(l>r)swap(l,r);
            l++;if(l>r)return 0;
            int tt=Log[r-l+1];
            return min(t[l][tt],t[r-(1<<tt)+1][tt]);
        }
    }A,B;
    void work(int l,int r,int j){
        int pre=B.ask(A.n-r+1,A.n-l+2),las=A.ask(l,r+1);
        l-=pre;r+=las;
        res+=max(0,r-l+1-K*j+1);
    }
    int main(){
        Log[1]=0;
        for(int i=2;i<M;i++)Log[i]=Log[i>>1]+1;
        int T;scanf("%d",&T);
        while(T--){
            scanf("%d",&K);
            scanf("%s",A.s+1);
            A.n=strlen(A.s+1);A.m=30;
            if(K==1){
                res=A.n;
                printf("%lld\n",res*(res+1)/2);
                continue;
            }else res=0;
    
    
            for(int i=1;i<=A.n;i++) B.s[A.n-i+1]=A.s[i];
            B.s[A.n+1]=0;
            B.n=A.n;
            B.m=A.m;
            A.getsa();B.getsa();
            A.rmq();B.rmq();
    //        for(int i=1;i<=A.n;i++)cout<<A.sa[i]<<" ";cout<<endl;
            for(int j=1;j<=A.n/2;j++){
                int las=1;
                for(int i=j+1;i<=A.n;i+=j){
                    if(A.ask(las,i)>=j)continue;
                    work(las,i-1,j);
                    if(i+j-1<=A.n)las=i;
                    else las=0;
                }
                if(las)work(las,A.n,j);
            }
            printf("%lld\n",res);
        }
        return 0;
    }

[2019 Multi-University Training Contest 8]: http://acm.hdu.edu.cn/search.php?field=problem&key=2019+Multi-University+Training+Contest+8&source=1&searchmode=source