洛谷P3121 审查(黄金)Censoring(Gold) [USACO15FEB] AC自动机

时间：2021-05-10 19:41:18

正解:AC自动机

解题报告:

传送门!

啊我好呆啊其实就挺模板题的,,,只是要一个栈搞一下,,,然后我就不会了,,,是看了题解才get的,,,QAQ

然后写下解法趴QwQ

首先看到多串匹配不难想到AC自动机?问题只是在于删了某个字符串之后怎么继续匹配下去嘛QwQ

然后我就卡这儿了QAQ

正解其实并不难想到,,,就可以开一个栈,记录一路上经过的ac自动机上的节点的编号,然后每次删了一个串之后把now跳到这个串的前一位的那个编号位置就好

补充一个恶心的小细节,,,

就是这题不输出换行会莫名其妙WA在第七个点,,,所以记得在结尾输出换行:D

overr

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define ll long long

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=1e5+,inf=1e9;

int n,nod_cnt,stck[N],lth,nw,top;

struct nod{int to[],fail,l;}tr[N*];

char ch[N],str[N],as[N];

queue<int>Q;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:x;

}

il void insert(char *s)

{

    ri lth=strlen(s+),nw=;

    rp(i,,lth)

    {

        if(!tr[nw].to[s[i]-'a'+])tr[nw].to[s[i]-'a'+]=++nod_cnt;

        nw=tr[nw].to[s[i]-'a'+];

    }

    tr[nw].l=lth;

}

il void bfs()

{

    rp(i,,)if(tr[].to[i])Q.push(tr[].to[i]);

    while(!Q.empty())

    {

        ri nw=Q.front();Q.pop();

        rp(i,,)

            if(tr[nw].to[i])Q.push(tr[nw].to[i]),tr[tr[nw].to[i]].fail=tr[tr[nw].fail].to[i];

            else tr[nw].to[i]=tr[tr[nw].fail].to[i];

    }

}

int main()

{

//    freopen("3121.in","r",stdin);freopen("3121.out","w",stdout);

    scanf("%s",str+);lth=strlen(str+);n=read();while(n--){scanf("%s",ch+);insert(ch);}bfs();

    rp(i,,lth)

    {

        stck[++top]=nw;as[top]=str[i];

        nw=tr[nw].to[str[i]-'a'+];

        if(tr[nw].l)top-=tr[nw].l,nw=stck[top+];

    }

    rp(i,,top)printf("%c",as[i]);printf("\n");

    return ;

}

这儿是代码!

相关文章