BZOJ3940: [Usaco2015 Feb]Censoring && BZOJ3942: [Usaco2015 Feb]Censoring

题目大意:

自己看.

题解:

利用AC自动机顺序扫描.

在AC自动机上的每个终止节点上记录串的长度.

每当发现完全匹配到某一个串,就将当前状态回退[串的长度]那么多,回到那个节点继续.

实在不懂的就看代码吧.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
#define N 100010
char s1[N],s2[N];
int tr[N][26],cnt,fail[N],len[N];
bool end[N],del[N];
int stack[N],top,ins[N];
int main(){
    scanf("%s",s1+1);
    int n=strlen(s1+1),i,j,m,_n;
    scanf("%d",&m);
    int p;
    while(m--){
        scanf("%s",s2+1);
        _n=strlen(s2+1);
        for(p=0,i=1;i<=_n;++i){
            if(!tr[p][s2[i]-'a'])
                tr[p][s2[i]-'a']=++cnt;
            p=tr[p][s2[i]-'a'];
        }
        end[p]=1;
        len[p]=_n;
    }
    queue<int>q;
    for(i=0;i<26;++i)
        if(tr[0][i])
            q.push(tr[0][i]);
    int u,v,r;
    while(!q.empty()){
        u=q.front();
        q.pop();
        for(i=0;i<26;++i){
            if((v=tr[u][i])){
                q.push(v);
                for(r=fail[u];r&&!tr[r][i];r=fail[r]);
                end[v]|=end[fail[v]=tr[r][i]];
            }
            else
                tr[u][i]=tr[fail[u]][i];
        }
    }
    for(p=0,i=1;i<=n;++i){
        stack[++top]=i;
        if(end[ins[i]=p=tr[p][s1[i]-'a']]){
            for(j=1;j<=len[p];++j)
                del[stack[top--]]=1;
            p=ins[stack[top]];
        }
    }
    for(i=1;i<=n;++i)
        if(!del[i])
            putchar(s1[i]);
    return 0;
}