P5357 【模板】AC自动机（二次加强版）

思路

这题可以同时作为AC自动机和SAM的模板啊喂

AC自动机

对T建出AC自动机，把S在上面匹配，然后记录每个点被经过的次数，最后统计一次即可（暴力跳fail的复杂度是不对的）

SAM

对S建出SAM，然后每次把T在上面匹配，如果匹配长度等于T的长度，输出出现次数，否则输出0

但是卡了SAM的空间

代码

AC自动机

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

int trans[200200][26],fail[200200],ends[200200],cnt[200200],Nodecnt=0,root=0,n;

char s[2000200];

void insert(char *s,int len,int inq){

    int p=root;

    for(int i=0;i<len;i++){

        if(!trans[p][s[i]-'a'])

            trans[p][s[i]-'a']=++Nodecnt;

        p=trans[p][s[i]-'a'];

    }

    ends[inq]=p;

}

queue<int> q;

void get_AC(void){

    for(int i=0;i<26;i++)

        if(trans[root][i]){

            fail[trans[root][i]]=root;

            q.push(trans[root][i]);

        }

    while(!q.empty()){

        int x=q.front();

        q.pop();

        for(int i=0;i<26;i++){

            if(trans[x][i]){

                fail[trans[x][i]]=trans[fail[x]][i];

                q.push(trans[x][i]);

            }

            else

                trans[x][i]=trans[fail[x]][i];

        }

    }

}

int in[2000200];

void topu(void){

    for(int i=1;i<=Nodecnt;i++)

        in[fail[i]]++;

    for(int i=1;i<=Nodecnt;i++)

        if(!in[i])

            q.push(i);

    while(!q.empty()){

        int x=q.front();

        q.pop();

        cnt[fail[x]]+=cnt[x];

        in[fail[x]]--;

        if(!in[fail[x]])

            q.push(fail[x]);

    }

}

int main(){

    scanf("%d",&n);

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

        scanf("%s",s);

        insert(s,strlen(s),i);

    }

    get_AC();

    scanf("%s",s);

    int lent=strlen(s),p=root;

    for(int i=0;i<lent;i++){

        p=trans[p][s[i]-'a'];

        cnt[p]++;

    }

    topu();

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

        printf("%d\n",cnt[ends[i]]);

    }

    return 0;

}

SAM

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <string>

#include <iostream>

#include <queue>

using namespace std;

int maxlen[1001000*2],trans[1001000*2][26],suflink[1001000*2],n,Nodecnt=1,len,endpos[1001000*2];

char S[1001000];

string T[200100];

int New_state(int _maxlen,int *_trans,int _suflink){

    ++Nodecnt;

    maxlen[Nodecnt]=_maxlen;

    if(_trans)

        for(int i=0;i<26;i++)

            trans[Nodecnt][i]=_trans[i];

    suflink[Nodecnt]=_suflink;

    return Nodecnt;

}

int add_len(int u,int c){

    int z=New_state(maxlen[u]+1,NULL,0);

    endpos[z]=1;

    while(u&&trans[u][c]==0){

        trans[u][c]=z;

        u=suflink[u];

    }

    if(!u){

        suflink[z]=1;

        return z;

    }

    int v=trans[u][c];

    if(maxlen[v]==maxlen[u]+1){

        suflink[z]=v;

        return z;

    }

    int y=New_state(maxlen[u]+1,trans[v],suflink[v]);

    suflink[z]=suflink[v]=y;

    while(u&&trans[u][c]==v){

        trans[u][c]=y;

        u=suflink[u];

    }

    return z;

}

int ranks[1001000*2],barrel[1001000*2];

void c_sort(int n,int lim){

    memset(barrel,0,sizeof(barrel));

    for(int i=1;i<=Nodecnt;i++)

        barrel[maxlen[i]]++;

    for(int i=1;i<=lim;i++)

        barrel[i]+=barrel[i-1];

    for(int i=1;i<=Nodecnt;i++)

        ranks[barrel[maxlen[i]]--]=i;

}

int main(){

    scanf("%d",&n);

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

        cin>>T[i];

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

    len=strlen(S+1);

    int last=1;

    for(int i=1;i<=len;i++)

        last=add_len(last,S[i]-'a');

    c_sort(Nodecnt,len);

    for(int i=Nodecnt;i>=1;i--)

        endpos[suflink[ranks[i]]]+=endpos[ranks[i]];

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

        int lent=T[i].length();

        int nowp=1,matchlen=0;

        for(int j=0;j<lent;j++){

            if(trans[nowp][T[i][j]-'a']){

                matchlen++;

                nowp=trans[nowp][T[i][j]-'a'];

            }

            else{

                while(nowp&&trans[nowp][T[i][j]-'a']==0)

                    nowp=suflink[nowp];

                if(!nowp){

                    nowp=1;

                    matchlen=0;

                }

                else{

                    matchlen=maxlen[nowp]+1;

                    nowp=trans[nowp][T[i][j]-'a'];

                }

            }

        }

        if(matchlen==lent){

            // int ans=0;

            // while(nowp){

            //     ans+=endpos[nowp];

            //     nowp=suflink[nowp];

            // }

            printf("%d\n",endpos[nowp]);

        }

        else{

            printf("0\n");

        }

    }

    return 0;

}