UVA10829 L-Gap Substrings（后缀数组+ST表）

后缀数组+ST表。
代填的坑。
\(Code\ Below:\)
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=100000+10;

int n,m,L,h[maxn],Min[maxn][18],sa[maxn],tax[maxn],rnk[maxn],tp[maxn];

char s[maxn];ll ans;

void SA(){

    int i,k,p;m=128;

    for(i=1;i<=n;i++) rnk[i]=s[i];

    for(i=1;i<=m;i++) tax[i]=0;

    for(i=1;i<=n;i++) tax[rnk[i]]++;

    for(i=1;i<=m;i++) tax[i]+=tax[i-1];

    for(i=n;i>=1;i--) sa[tax[rnk[i]]--]=i;

    for(k=1,p=0;k<n;m=p,k<<=1){

        p=0;

        for(i=n-k+1;i<=n;i++) tp[++p]=i;

        for(i=1;i<=n;i++) if(sa[i]>k) tp[++p]=sa[i]-k;

        for(i=1;i<=m;i++) tax[i]=0;

        for(i=1;i<=n;i++) tax[rnk[i]]++;

        for(i=1;i<=m;i++) tax[i]+=tax[i-1];

        for(i=n;i>=1;i--) sa[tax[rnk[tp[i]]]--]=tp[i];

        swap(rnk,tp);rnk[sa[1]]=p=1;

        for(i=2;i<=n;i++) rnk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+k]==tp[sa[i]+k])?p:++p;

    }

}

void getheight(){

    int i,j,p=0;

    for(i=1;i<=n;i++) rnk[sa[i]]=i;

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

        j=sa[rnk[i]-1];if(p) p--;

        while(s[i+p]==s[j+p]) p++;

        h[rnk[i]]=p;

    }

    for(i=1;i<=n;i++) Min[i][0]=h[i];

    for(j=1;j<18;j++)

        for(i=1;i+(1<<j)-1<=n;i++) Min[i][j]=min(Min[i][j-1],Min[i+(1<<(j-1))][j-1]);

}

int query(int l,int r){

    int k=log2(r-l+1);

    return min(Min[l][k],Min[r-(1<<k)+1][k]);

}

int LCP(int x,int y){

    int l=rnk[x],r=rnk[y];

    if(l==r) return n-sa[l]+1;

    if(l>r) swap(l,r);

    return query(l+1,r);

}

int LCS(int x,int y){

    return LCP(2*n-x+2,2*n-y+2);

}

int main()

{

    int T;

    scanf("%d",&T);

    for(int Case=1;Case<=T;Case++){

        #define mem(x) memset(x,0,sizeof(x))

        mem(s);mem(sa);mem(tax);mem(rnk);mem(tp);ans=0;

        scanf("%d%s",&L,s+1);n=strlen(s+1);

        for(int i=1;i<=n;i++) s[2*n-i+2]=s[i];

        s[n+1]='$';n=2*n+1;

        SA();getheight();n/=2;

        int x,y,lcp,lcs,num;

        for(int len=1;len+L<=n;len++)

            for(int i=1;i+len+L<=n;i+=len){

                x=i;y=i+len+L;

                lcp=min(LCP(x,y),len);

                lcs=min(LCS(x,y),len);

                num=lcp+lcs-(lcp>0&&lcs>0);

                ans+=max(num-len+1,0);

            }

        printf("Case %d: %lld\n",Case,ans);

    }

    return 0;

}
巴特西

UVA10829 L-Gap Substrings（后缀数组+ST表）

最新文章

热门文章
