bzoj3940censoring

关键词：

把上题的KMP改成AC自动机。

注意root必须是0。因为root其实是NULL的意思。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxn 500050
using namespace std;
char t[maxn],s[maxn];
int cases,l,son[maxn][30],fail[maxn],fath[maxn],root,tot=0,pre[maxn],ts[maxn],len[maxn];
queue <int> q;
bool flag[maxn];
void insert()
{
    int now=root;
    for (int i=0;i<l;i++)
    {
        int nb=s[i]-‘a‘+1;
        if (!son[now][nb]) son[now][nb]=++tot;
        now=son[now][nb];
        if (i==l-1) len[now]=l;
    }
}
void build_AC()
{
    q.push(root);
    while (!q.empty())
    {
        int head=q.front();q.pop();
        for (int i=1;i<=26;i++)
        {
            if (son[head][i])
            {
                if (head!=root)fail[son[head][i]]=son[fail[head]][i];
                else fail[son[head][i]]=root;
                q.push(son[head][i]);
            }
            else son[head][i]=son[fail[head]][i];
        }
    }
}
void match_AC()
{
    int now=root;ts[0]=1;
    for (int i=1;i<=l;i++)
    {
        int nb=t[i-1]-‘a‘+1;
        while (now!=root && !son[now][nb]) now=fail[now];
        if (son[now][nb]) now=son[now][nb];
        ts[i]=now;
        if (len[now])
        {
            int p=i;
            for (int j=1;j<=len[now];j++)
            {
                flag[p-1]=true;
                p=pre[p];
            }
            pre[i+1]=p;now=ts[p];
        }
    }
}
int main()
{
    scanf("%s",t);
    scanf("%d",&cases);root=tot=0;
    for (int i=1;i<=cases;i++)
    {
        scanf("%s",s);
        l=strlen(s);insert();
    }
    build_AC();
    l=strlen(t);for (int i=1;i<=l;i++) pre[i]=i-1;
    match_AC();
    for (int i=0;i<l;i++)
        if (!flag[i]) printf("%c",t[i]);
    printf("
");
    return 0;
} 

bzoj3940censoring

把上题的KMP改成AC自动机。注意root必须是0。因为root其实是NULL的意思。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#definemaxn500050usingnamespacestd;chart[m 查看详情

bzoj3940[usaco2015feb]censoring*

bzoj3940[Usaco2015Feb]Censoring题意:有一个S串和一大堆T串，不断地在S串里找最早出现的T串，然后将其删除。S串≤100000，T串总长度≤100000。题解：对所有T串建AC自动机，然后同bzoj3942。注意，本题的AC自动机必须利用所有fail函数建成... 查看详情

bzoj3940censoring题解（ac自动机）(代码片段)

题目描述FarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplenty ofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatest issueco 查看详情

bzoj3940:[usaco2015feb]censoring--ac自动机

3940:[Usaco2015Feb]CensoringTimeLimit: 10Sec  MemoryLimit: 128MBDescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplenty ofmaterial 查看详情

[bzoj3940][usaco2015feb]censoring

最近做题成双成对？不是双倍经验就是两题同解。3940  3942给定字典，给定字符串，删去字符串中所有字典内单词。保证不会出现二者包含状况。$nleq1e5,sumlenleq1e5$AC自动机裸题。build出AC自动机后从左到右插入文本串，同时... 查看详情

bzoj3940:[usaco2015feb]censoring

给个长度<=1e5的串s，再给n个模板串总长不超1e5，每次把s中起始位置最早的一个模板串删掉，求最后剩的串。AC自动机，开个栈记一下每次走到哪里，匹配成功后直接在栈里找到这一串的初始位置对应自动机上的节点，从而回... 查看详情

bzoj3940[usaco2015feb]censoring

【题目描述】FJ把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过10^5的字符串S。他有一个包含n个单词的列表，列表里的n个单词记为t_1...t_N。他希望从S中删除这些单词。 FJ每次在S中找到最早出现的列表中的单词(... 查看详情

bzoj3940&&bzoj3942

方法就是维护一个动态栈记录栈的每一位匹配到串的哪一位的编号第一道kmp第二道ac自动机自己理会#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintM=1000055;charstack[M],s[M],t[M],f[M],next[M];intlen,top; 查看详情

bzoj3942censoring

KMP。怎么描述做法呢。。。“持久化”一下？#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#definemaxn1000050usingnamespacestd;chars[maxn],t[maxn];intl1,l2,nxt[maxn],pre[maxn] 查看详情

bzoj3940

AC自动机复习一下。。。可惜又写错了我们发现就是把单词建成ac自动机，然后把串在ac自动机上跑一遍，每到一个单词结束点就删除，删除是利用栈，每次弹出单词长度个字符就可以了发现两个小问题，strlen很慢，不能写在循环... 查看详情

bzoj3942:[usaco2015feb]censoring

3942:[Usaco2015Feb]CensoringTimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 404  Solved: 221[Submit][Status][Discuss]DescriptionFarmerJohnhaspurchasedasubscriptiont 查看详情

考后反思（bzoj3940bzoj4899bzoj3307）(代码片段)

...最后骗了五分 考后主要讲一下第二题：记忆的轮廓（bzoj4899）和第三题：雨天 查看详情

bzoj3942[usaco2015feb]censoring*

bzoj3942[Usaco2015Feb]Censoring题意：有一个S串和一个T串，不断地在S串里匹配T串，然后将其删除。S串、T串长度≤1000000。题解：用1、2两个栈，每次将S串的当前字符压入1栈，当前匹配到T串的位置压入2栈，如果匹配出一个T串，则让1... 查看详情

bzoj3942——censoring（kmp）(代码片段)

传送门前面一大串的英文题面被我忽略了KMP+栈只需通过维护一个栈就可以了(*￣︶￣)（我懒得多写）1#include<cstdio>2#include<iostream>3#include<cmath>4#include<cstring>5#include<algorithm>6#include<cstdlib>7usingn 查看详情

bzoj_3942_[usaco2015feb]censoring_kmp

BZOJ_3942_[Usaco2015Feb]Censoring_KMPDescription有一个S串和一个T串，长度均小于1,000,000，设当前串为U串，然后从前往后枚举S串一个字符一个字符往U串里添加，若U串后缀为T，则去掉这个后缀继续流程。InputThefirstlinewillcontainS.Thesecondlinewill... 查看详情

洛谷p3121[usaco15feb]审查（黄金）censoring(gold)ac自动机+栈

这个和bzoj同名题不一样，有多个匹配串但是思路是一样的，写个AC自动机，同样是开两个栈，一个存字符，一个存当前点在trie树上的位置，然后如果到了某个匹配串的末尾，则弹栈#include<iostream>#include<cstdio>#include<cstr... 查看详情

bzoj1088:[scoi2005]扫雷mine

1088:[SCOI2005]扫雷MineTimeLimit:10Sec  MemoryLimit:162MBSubmit:3940  Solved:2324[Submit][Status][Discuss]Description　　相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余&... 查看详情

bzoj1096[zjoi2007]仓库建设（斜率优化）

1096:[ZJOI2007]仓库建设TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 3940  Solved: 1736Description　　L公司有N个工厂，由高到底分布在一座山上。如图所示，工厂1在山顶，工厂N在山脚。由于这座山处于高原内陆地区（... 查看详情