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

· · 题解

为什么楼下奆佬都用栈啊QwQ

这题用链表也可以啊

先把单词建成ac机，然后把文章放进去跑一遍，删除的时候用链表标记就可以了。

但是这里有个问题：

删除完之后，i还要继续增加，但是u（自动机中的节点）还是现在的，所以要把u还原到删除之前的状态。

以样例为例：

begintheescapexecutionatthebreakofdawn 
2 
escape 
execution

第一次匹配到escape，此时i在13（也就是字符p的位置），前面与后面接在一起了，要匹配execution，但此时u还是在匹配完escape（也就是i在p的位置）时的位置，不能继续匹配，需要调到execution的开头时的位置才可以继续匹配，所以需要再开一个bk数组存储当匹配到第i位时，u的位置。

code:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char wz[5200010];//文章
char dc[5200010];//单词
int ch[5200010][30];//Trie树,ch[u][i]表示u号节点的转移边i连接的节点
int bo[5200010];//结尾标记
int ans[5200010];
int T;
int n,m;
int tot=1;//节点个数
bool bs=0;//开头的处理（如果单词出现在开头的话就会出锅，要单独处理）
int que[5200010];
int nxt[5200010];//失配指针
int f[5200010];
int pre[5200010];//链表的下一个（这里nxt用掉了只能用pre，由于英文不好搞反了，本来应该是上一个的）
int per[5200010];//上一个
int bk[5200010];//bk
int ff(char c){//把字符转换为数字
    return c-'a';
}
void insert(char *s){//插入
    int u=1;
    int len=strlen(s);
    for(int i=0;i<len;i++){
        int c=ff(s[i]);
        if(!ch[u][c]){
            ch[u][c]=++tot;
        }
        u=ch[u][c];
    }
    bo[u]++;
    f[u]=len;
}
void bfs(){//构建失配边
    nxt[1]=0;
    for(int i=0;i<26;i++){
        ch[0][i]=1;
    }
    que[1]=1;
    for(int head=1,tail=1;head<=tail;head++){
        int u=que[head];
        for(int i=0;i<26;i++){
            if(!ch[u][i]){
                ch[u][i]=ch[nxt[u]][i];
            }
            else{
                que[++tail]=ch[u][i];
                nxt[ch[u][i]]=ch[nxt[u]][i];
            }
        }
    }
}
void query(){//查询
    int u=1;
    int len=strlen(wz);
    for(int i=0;i<len;i++){
        pre[i]=i+1;
        per[i]=i-1;
    }//初始化
    for(int i=0;i<len;i=pre[i]){
        int c=ff(wz[i]);
        u=ch[u][c];
        bk[i]=u;//标记
        if(bo[u]){//如果匹配到了
            int pr=i;//pr代表i往前跳m个位置（也就是找到单词时单词开头的位置）
            for(int k=1;k<=f[u];k++){
                pr=per[pr];
            }
            if(pr<0){//注意！如果往前跳m位时pr<0，就说明在开头时就发现了单词
                pr=0;
                bs=1;
            }
            int now=pre[i];
            pre[pr]=now;
            per[now]=pr;//把中间一段删掉
            u=bk[pr];
        }
    }
}
int main() {
    tot=1;
    scanf("%s",wz);
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%s",dc);
        insert(dc);//插入
    }
    bfs();
    query();
    int len=strlen(wz);
    for(int i=0;i<len;i=pre[i]){
        if(i==0 && bs) continue;//如果有开头标记说明开始那一段已经删掉了，要跳过
                        //不然就会多输出一个字符
        printf("%c",wz[i]);
    }
    printf("\n");//第七个点有坑，要换行...
    return 0;
}