点此看题面

大致题意： 给你一个文本串和\(N\)个模式串，要你将每一个模式串从文本串中删去。（此题是【BZOJ3942】[Usaco2015 Feb]Censoring的升级版）

\(AC\)自动机

这是一道\(AC\)自动机的简单运用题。

题解

我们可以用一个\(ans[\) \(]\)字符数组来存储最后的答案，并用一个\(lst[\) \(]\)数组来记录字符串中每一位上次被访问时所到达的\(Trie\)上的节点。

如果找到了一个长度为\(len\)的模式串要删去，我们可以将\(ans\)的长度\(len_{ans}\)减去\(len\)，然后更新当前在\(Trie\)*问到的节点为\(lst[len_{ans}]\)。

这样不断操作，就可以求出答案了。

代码

#include<bits/stdc++.h>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define LL long long

#define ull unsigned long long

#define swap(x,y) (x^=y,y^=x,x^=y)

#define tc() (A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++)

#define SUM 100000

char ff[100000],*A=ff,*B=ff;

using namespace std;

int n,rt=1,tot=1,lst[SUM+5];

string st;

char ans[SUM+5];

struct Trie

{

    int Son[26],Next,Len;

}node[SUM+5];

queue<int> q;

inline void read(int &x)

{

    x=0;static char ch;

    while(!isdigit(ch=tc()));

    while(x=(x<<3)+(x<<1)+ch-48,isdigit(ch=tc()));

}

inline void read_string(string &x)

{

    x="";static char ch;

    while(isspace(ch=tc()));

    while(x+=ch,!isspace(ch=tc())) if(!(~ch)) return;

}

inline void Insert(string st)

{

    register int i,nxt,x=rt,len=st.length();

    for(i=0;i<len;++i)

    {

        if(!node[x].Son[nxt=st[i]-97]) node[x].Son[nxt]=++tot;

        x=node[x].Son[nxt];

    }

    node[x].Len=len;//在当前模式串最后到达的节点记录下当前模式串的长度

}

inline void GetNext()

{

    register int i,k;q.push(rt);

    while(!q.empty())

    {

        k=q.front(),q.pop();

        for(i=0;i<26;++i)

        {

            if(k^rt)

            {

                if(!node[k].Son[i]) node[k].Son[i]=node[node[k].Next].Son[i];

                else node[node[k].Son[i]].Next=node[node[k].Next].Son[i],q.push(node[k].Son[i]);

            }

            else

            {

                if(!node[k].Son[i]) node[k].Son[i]=rt;

                else node[node[k].Son[i]].Next=rt,q.push(node[k].Son[i]);

            }

        }

    }

}

inline void AC_Automation()

{

    register int i,j,x=rt,len=st.length(),len_ans=0;

    for(GetNext(),i=0;i<len;++i)

    {

        if(!(x=node[x].Son[(ans[++len_ans]=st[i])-97])) {lst[len_ans]=x=rt;continue;}

        lst[len_ans]=x;//用lst[]数组存储下当前位置所对应的Trie上的节点

        if(node[x].Len) len_ans-=node[x].Len,x=lst[len_ans];//如果当前位置上有一个字符串，就将其删去，并更新当前Trie上的节点

    }

    ans[len_ans+1]=0;

}

int main()

{

    register int i,j;register string s;

    for(read_string(st),read(n),i=1;i<=n;++i) read_string(s),Insert(s);

    return AC_Automation(),puts(ans+1),0;

}