[USACO15FEB] Censoring - AC自动机,栈

给定文章串 \(S\)，要从 \(S\) 中删去由 \(n\) 个单词构成的单词簿中的所有单词。每次找到最早出现的单词并且删除，重复操作到没有单词簿中的单词为止。输出最后的 \(S\)。

Solution

可以理解为每次碰到对应的单词就按若干下退格键

于是一个直观的想法是：我们把 \(S\) 扔到 ACAM 上跑，跑到匹配的结点就往父亲上跳若干次？

显然这样并不正确，我们应当要记录每个时刻所在的结点来实现退格

不难想到用栈来维护

一个栈记录结点编号，一个栈记录输出串

遇到匹配的情况，就两个栈一起弹出长度次

#include <bits/stdc++.h>
using namespace std;

int val[100005],ch[100005][26],fi[100005],n,m,ind,top,num[100005];
char str[100005],art[100005],pri[100005];

void insert(char *s){
    int len=strlen(s),p=0;
    for(int i=0;i<len;i++){
        int v=s[i]-'a';
        if(!ch[p][v]) ch[p][v]=++ind;
        p=ch[p][v];
    }
    val[p]=len; 
}

void build(){
    queue <int> q;
    for(int i=0;i<26;i++)
        if(ch[0][i])
            q.push(ch[0][i]);
    while(!q.empty()){
        int p=q.front(); q.pop();
        for(int i=0;i<26;i++)
            if(ch[p][i]) fi[ch[p][i]]=ch[fi[p]][i], q.push(ch[p][i]);
            else ch[p][i]=ch[fi[p]][i];
    }
}

int query(char *s){
    int len=strlen(s), p=0, ans=0;
    for(int i=0;i<len;i++){
        p=ch[p][s[i]-'a'];
        ++top;
        num[top]=p;
        pri[top]=s[i];
        if(val[p]>0) {
            top-=val[p];
            if(!top) p=0; 
            else p=num[top];
        }
    }
    return top;
}

int main(){
    scanf("%s",&art);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%s",str), insert(str);
    build();
    query(art);
    for(int i=1;i<=top;i++) printf("%c",pri[i]);
}

[USACO15FEB] Censoring - AC自动机,栈

原文：https://www.cnblogs.com/mollnn/p/12450019.html