Censoring

https://loj.ac/problem/10059

题目描述

　　给出模式串和若干匹配串，求从模式串中删除所有匹配串后的结果（删除后其余字符串前移）。

思路

　　多字符串的匹配问题，显然可以用可以AC自动机维护。接下来就是处理删除的问题，如果我们不断删除后从头开始匹配，肯定会T掉。我们可以考虑与Censoring类似的思想，用一个栈维护，把每个点入栈，匹配到就把字符串长度数量的点出栈，从栈顶开始从新匹配。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int ch[MAXN][27],tot,nxt[MAXN],f[MAXN],st[MAXN],ed[MAXN];
char s[MAXN],ss[MAXN];
void clear()
{
    memset(ch,0,sizeof(ch));
    memset(ed,0,sizeof(ed));
    memset(nxt,0,sizeof(nxt));
    tot=0;
}
void insert(char *s)
{
    int u=0,len=strlen(s);
    for(int i=0;i<len;i++)
    {
        int c=s[i]-‘a‘;
        if(!ch[u][c])ch[u][c]=++tot;
        u=ch[u][c];
    }
    ed[u]=len;
}
queue<int>q;
void bfs()
{
    for(int i=0;i<26;i++)
        if(ch[0][i]){q.push(ch[0][i]);nxt[ch[0][i]]=0;}
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=0;i<26;i++)
        {
            if(!ch[u][i])ch[u][i]=ch[nxt[u]][i];
            else
            {
//                cout<<u<<‘ ‘<<i<<endl;
                q.push(ch[u][i]);
                int v=nxt[u];
                nxt[ch[u][i]]=ch[v][i];
            }
        }
    }
}
int main() 
{
    int n;
    clear();
    scanf(" %s",ss);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf(" %s",s);
        insert(s);
//        printf("%s\n",s);
    }
    bfs();
    int m=strlen(ss),top=0,u=0;
    for(int i=0;i<m;i++)
    {
        int c=ss[i]-‘a‘;
        f[i]=u=ch[u][c];
        st[++top]=i;
//        cout<<ss[i]<<‘ ‘<<u<<endl;
        if(ed[u])
        {
            top-=ed[u];
            u=f[st[top]];
        }
    }
    for(int i=1;i<=top;i++)
        putchar(ss[st[i]]);
    return 0;
}