BZOJ-3940: [Usaco2015 Feb]Censoring

Description

给你一个母串s，给你n个互不包含的子串t。一直在s中删除一个子串t构成新的s，最后不含有任何一个子串t得到的s。长度<=10^5

由于是多个串，所以需要建AC自动机，然后匹配的过程中维护一个栈，记录路径节点的位置，到危险节点就回溯。注意栈底元素应为root

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,tot=1;
struct trie
{
    int c[26],fail,dan;
}t[101000];
char s[101000],st[101000];
int q[101000];
char z[101000];
int main()
{
    scanf("%s",s); scanf("%d",&n);
    int p,len;
    for(int i=1;i<=n;++i)
    {
        scanf("%s",st);
        p=1; len=strlen(st);
        for(int j=0;j!=len;++j)
        {
            if(!t[p].c[st[j]-'a']) t[p].c[st[j]-'a']=++tot;
            p=t[p].c[st[j]-'a'];
        }
        t[p].dan=len;
    }
    int l=1,r=0;
    for(int i=0;i!=26;++i)
    {
        if(t[1].c[i]) q[++r]=t[1].c[i],t[t[1].c[i]].fail=1;
        else t[1].c[i]=1;
    }
    while(l<=r)
    {
        p=q[l++];
        for(int i=0;i!=26;++i)
        {
            if(t[p].c[i]) q[++r]=t[p].c[i],t[t[p].c[i]].fail=t[t[p].fail].c[i];
            else t[p].c[i]=t[t[p].fail].c[i];
        }
    }
    len=strlen(s); p=1; r=0; q[0]=1;
    for(int i=0;i!=len;++i)
    {
        p=t[p].c[s[i]-'a']; q[++r]=p; z[r]=s[i];
        if(t[p].dan) r-=t[p].dan,p=q[r];
    }
    z[++r]='\0';
    printf("%s\n",z+1);
    return 0;
}