题解 P3121 【[USACO15FEB]审查（黄金）Censoring (Gold)】

· · 题解

既然没人搞题解，那我就来份题解吧。

这个题实际上是用栈+AC自动机实现O（n）效率的。

再次吐槽一下数据，纯暴力都能过93分，数据水的不要不要的。

两种做法：

法1：栈+AC自动机

开两个栈，一个记录当前节点扫到AC自动机的哪个地方了，一个记录当然栈内合法的字符，每当发现一个能删去的字符串的时候，只需要把两个栈都减去字符串长度即可，把now修改一下，继续往后扫即可，最后输出第二个栈即可。

法2：暴力玄学AC自动机

不用栈，sign记录当前节点扫到AC自动机的哪个地方，我们开一个next数组和pre数组，记录当前这个点的后面那个点是几号、前面那个点是几号，每当发现一个能删去的字符串的时候，暴力跳到字符串头上的pre，将其的next修改为字符串尾的next，修改一下now，继续扫就行，这样也能A。因为要O（n）预处理一下next和pre，所以会比法1稍微慢一丢丢。（鬼知道我为啥玄学的法2卡评测机的比法1跑的快几毫秒）

法1代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
char s[100001],ori[100001];
int n,tot,w,top;
int trie[100001][26],fail[100001],heap[100001],sign[100001];
int isend[100001];
void insert(char *s){
    int now=0,len=strlen(s);
    for(int i=0;i<len;i++){
        int x=s[i]-'a';
        if(!trie[now][x])trie[now][x]=++tot;
        now=trie[now][x];
    }
    isend[now]=len;
}
void makefail(){
    queue<int> q;
    for(int i=0;i<26;i++)
    if(trie[0][i])q.push(trie[0][i]);
    while(!q.empty()){
        int now=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(!trie[now][i]){
                trie[now][i]=trie[fail[now]][i];
                continue;
            }        
            fail[trie[now][i]]=trie[fail[now]][i];
            q.push(trie[now][i]);
        }
    }
}
void solve(char *s){
    int now=0,len=strlen(s),i=0;
    w=0;
    while(i<len){
        int x=s[i]-'a';
        now=trie[now][x];
        sign[++top]=now;
        heap[top]=i;
        if(isend[now]){
            top-=isend[now];
            if(!top) now=0;
            else now=sign[top];
        }
        i++;
    }
}
int main()
{
    scanf("%s",s);
    scanf("%d",&n);
    int len=strlen(s);
    for(int i=1;i<=n;i++){
        scanf("%s",ori);
        insert(ori);
    }
    makefail();
    solve(s);
    for(int i=1;i<=top;i++)
    printf("%c",s[heap[i]]);
    return 0;
}