bzoj3940&&bzoj3942 Ac自动机||kpm算法

方法就是维护一个动态栈 记录栈的每一位匹配到串的哪一位的编号 第一道kmp第二道ac自动机 自己理会

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=;

char stack[M],s[M],t[M],f[M],next[M];

int len,top;

void getfail(){

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

        int j=f[i];

        while(j&&t[i]!=t[j]) j=f[j];

        f[i+]=(t[i]==t[j]?j+:);

    }

}

int main()

{

    scanf("%s %s",s,t);

    int L=strlen(s); len=strlen(t); getfail();

    for(int i=;i<L;i++){

        stack[++top]=s[i];

        int j=next[top-];

        while(j&&t[j]!=stack[top]) j=f[j];

        if(t[j]==stack[top]) j++;

        next[top]=j;

        if(j==len) top-=len;

    }

    for(int i=;i<=top;i++) printf("%c",stack[i]);

    return ;

}

//同bzoj3942

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int size=,M=;

char s[M],T[M],stack[M];

int next[M],top,n;

struct node{

    int sum,a[M][],last[M],fail[M],val[M];

    int id(char s) {return s-'a'+;}

    void insert(char s[]){

        int k=,L=strlen(s);

        for(int i=;i<L;i++){

            int now=id(s[i]);

            if(!a[k][now]) a[k][now]=++sum;

            k=a[k][now];

        }

        val[k]=L;

    }

    void getfail(){

        int q[M],k=,head=,tail=;

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

            int now=a[][i];

            if(now) q[tail++]=now;

        }

        while(head!=tail){

            int x=q[head++];

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

                int now=a[x][i];

                if(!now) { a[x][i]=a[fail[x]][i];continue;}

                q[tail++]=now;

                fail[now]=a[fail[x]][i];

                last[now]=val[fail[now]]?fail[now]:last[fail[now]];

            }

        }

    }

    void Ac_boy(){

        int now=,L=strlen(T);

        for(int i=;i<L;i++){

            int d=id(T[i]);

            stack[top]=T[i];

            now=a[now][d];

            next[top]=now;

            if(val[now]) top-=val[now],now=next[top];

            else if(last[now]) top-=val[last[now]],now=next[top];

            top++;

        }

    }

}node;

int main()

{

    scanf("%s",T);

    int n; scanf("%d",&n);

    while(n--) scanf("%s",s),node.insert(s);

    node.getfail(); node.Ac_boy();

    for(int i=;i<top;i++) putchar(stack[i]);

    return ;

}