HDU 6194 string string string（后缀自动机）

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3238

【题目大意】

　　给出一个字符串求其出现恰好k次的子串数量

【题解】

　　对串建立AC自动机，所有right值为k的节点的value值的和就是答案

【代码】

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int N=200010;

char s[N];

struct SAM{

    int p,q,np,nq,cnt,lst,a[N][26],l[N],f[N],tot;

    int Tr(char c){return c-'a';}

    int val(int c){return l[c]-l[f[c]];}

    SAM(){cnt=0;lst=++cnt;}

    void Initialize(){

        memset(l,0,sizeof(int)*(cnt+1));

        memset(f,0,sizeof(int)*(cnt+1));

        for(int i=0;i<=cnt;i++)for(int j=0;j<26;j++)a[i][j]=0;

        cnt=0;lst=++cnt;

    }

    void extend(int c){

        p=lst;np=lst=++cnt;l[np]=l[p]+1;

        while(!a[p][c]&&p)a[p][c]=np,p=f[p];

        if(!p){f[np]=1;}

        else{

            q=a[p][c];

            if(l[p]+1==l[q])f[np]=q;

            else{

                nq=++cnt;l[nq]=l[p]+1;

                memcpy(a[nq],a[q],sizeof(a[q]));

                f[nq]=f[q]; f[np]=f[q]=nq;

                while(a[p][c]==q)a[p][c]=nq,p=f[p];

            }

        }

    }

    int b[N],x[N],r[N];

    void build(){

        scanf("%s",s+1);

        int len=strlen(s+1);

        for(int i=1;i<=len;i++)extend(Tr(s[i]));

        memset(r,0,sizeof(int)*(cnt+1));

        memset(b,0,sizeof(int)*(cnt+1));

        for(int i=1;i<=cnt;i++)b[l[i]]++;

        for(int i=1;i<=len;i++)b[i]+=b[i-1];

        for(int i=1;i<=cnt;i++)x[b[l[i]]--]=i;

        for(int i=p=1;i<=len;i++){p=a[p][Tr(s[i])];r[p]++;}

        for(int i=cnt;i;i--)r[f[x[i]]]+=r[x[i]];

    }

    void solve(){

        int ans=0,k;

        scanf("%d",&k);

        build();

        for(int i=1;i<=cnt;i++)if(r[x[i]]==k)ans+=val(x[i]);

        printf("%d\n",ans);

    }

}sam;

int T;

int main(){

    scanf("%d",&T);

    while(T--){

        sam.Initialize();

        sam.solve();

    }return 0;

}