BZOJ3940: [Usaco2015 Feb]Censoring【AC自动机】

3940: [Usaco2015 Feb]Censoring

【题目描述】

传送门

【题解】

和KMP的那道一样的,记住上一次匹配到的位置,然后继续匹配就可以了。

代码如下

#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=2e5+5;
int n,tot;
char s[MAXN],stk[MAXN],ch[MAXN];
struct AhoC{
    int hd,tl,que[MAXN],Son[MAXN][26],L[MAXN],pre[MAXN],P[MAXN],cnt;
    int get(char ch){return ch-'a';}
    void Insert(char *s,int i){
        int Now=0,Len=strlen(s);
        for(int i=0,w;i<Len;i++){
            if(!Son[Now][w=get(s[i])]) Son[Now][w]=++cnt;
            Now=Son[Now][w];
        }
        L[Now]=Len;
    }
    void Build(){
        hd=tl=0;
        for(int i=0;i<26;i++) if(Son[0][i]) que[++tl]=Son[0][i];
        while(hd^tl){
            int x=que[++hd];
            for(int i=0;i<26;i++)
            if(Son[x][i]){
                int f=pre[x];
                while(f&&!Son[f][i]) f=pre[f];
                pre[que[++tl]=Son[x][i]]=Son[f][i];
            }else Son[x][i]=Son[pre[x]][i];
        }
    }
    void Work(){
        int Len=strlen(s),Now=0;
        for(int i=0,w;i<Len;i++){
            Now=P[tot],w=get(stk[++tot]=s[i]);
            while(!Son[Now][w]&&Now) Now=pre[Now];
            if(Son[Now][w]&&L[Son[Now][w]]){tot-=L[Son[Now][w]],Now=P[tot];continue;}
            Now=Son[Now][w],P[tot]=Now;
        }
    }
}Tre;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%s%d",s,&n);
    for(int i=1;i<=n;i++) scanf("%s",ch),Tre.Insert(ch,i);
    Tre.Build();Tre.Work();
    for(int i=1;i<=tot;i++) putchar(stk[i]);
    putchar('\n');
    return 0;
} 

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部