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

从原来的单串匹配变成了多串匹配

好像也没什么特别不一样的地方

原来的做法是搞一个栈，之后一旦匹配到就往前弹栈

做法也一样

但是在\(AC\)自动机上暴力跳\(fail\)是要\(T\)的

我们并没有必要去暴力跳\(fail\)，只需要存下往后跳\(fail\)能跳到的成功的位置是哪里就好了

这个在预处理的时候处理一下就好了

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<stack>

#define LL long long

#define min(a,b) ((a)<(b)?(a):(b))

#define max(a,b) ((a)>(b)?(a):(b))

#define re register

#define maxn 100005

char S[maxn],T[maxn];

inline int read()

{

    char c=getchar();

    int x=0;

    while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();

    return x;

}

int son[maxn][26],flag[maxn],fail[maxn],vis[maxn],st[maxn],sta[maxn],to[maxn];

int n,cnt,top;

inline void ins()

{

    scanf("%s",S+1);

    int len=strlen(S+1);

    int now=0;

    for(re int i=1;i<=len;i++)

    {

        if(!son[now][S[i]-'a']) son[now][S[i]-'a']=++cnt;

        now=son[now][S[i]-'a'];

    }

    flag[now]=len;

}

inline void Build()

{

    std::queue<int> q;

    for(re int i=0;i<26;i++) if(son[0][i]) q.push(son[0][i]);

    while(!q.empty())

    {

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

        if(flag[fail[k]]) to[k]=fail[k];

            else to[k]=to[fail[k]];

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

        if(son[k][i]) fail[son[k][i]]=son[fail[k]][i],q.push(son[k][i]);

            else son[k][i]=son[fail[k]][i];

    }

}

inline void AC_query()

{

    int len=strlen(T+1);

    int now=0;

    for(re int i=1;i<=len;i++)

    {

        now=son[now][T[i]-'a'];

        st[++top]=now,sta[top]=i;

        for(re int j=now;j;j=to[j])

        if(flag[j])

        {

            int t=flag[j];

            while(t--) vis[sta[top--]]=1;

            now=st[top];

            break;

        }

    }

    for(re int i=1;i<=len;i++) if(!vis[i]) putchar(T[i]);

    putchar(10);

}

int main()

{

    scanf("%s",T+1);

    scanf("%d",&n);

    for(re int i=1;i<=n;i++) ins();

    Build();

    AC_query();

    return 0;

}

巴特西

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

最新文章

热门文章