正文

bzoj3940

123456  123456  2022-09-14  290

关键词：

AC自动机

复习一下。。。可惜又写错了

我们发现就是把单词建成ac自动机，然后把串在ac自动机上跑一遍，每到一个单词结束点就删除，删除是利用栈，每次弹出单词长度个字符就可以了

发现两个小问题，strlen很慢，不能写在循环里，danger必须在构造fail时全部传递好，否则在匹配时跑fail会达到n^2

至于这里danger为什么不转移，我也不是很清楚。。。大概是因为使用了trie图优化，并且不是统计单词出现次数，只是希望尽量找到靠前的单词删除

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, top;
char s[N], t[N], st[N];
int mark[N], last[N];
struct AC {
    int root, cnt;
    int danger[N], child[N][27], fail[N];
    void insert()
    {
        int now = root, len = strlen(t);
        for(int i = 0; i < len; ++i)
        {
            int p = t[i] - ‘a‘;
            if(child[now][p] == 0) child[now][p] = ++cnt;
            now = child[now][p];
        } 
        danger[now] = strlen(t);
    } 
    void build_fail()
    {
        queue<int> q;
        for(int i = 0; i < 26; ++i) if(child[root][i]) q.push(child[root][i]);
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            for(int i = 0; i < 26; ++i) 
            {
                if(child[u][i] == 0) child[u][i] = child[fail[u]][i];
                else
                {
                    fail[child[u][i]] = child[fail[u]][i];
                    q.push(child[u][i]);
                }
            }
        }
    }
    void put_string()
    {
        int now = root, len = strlen(s);
        for(int i = 0; i < len; ++i)
        {       
            st[++top] = s[i];
            now = child[now][s[i] - ‘a‘];
            last[top] = now;
            top -= danger[now];     
            now = last[top];
        }
    }
} ac;
int main()
{
    scanf("%s%d", s, &n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%s", t);
        ac.insert();
    } 
    ac.build_fail();
    ac.put_string();
    int cnt = 0;
    for(int i = 1; i <= top; ++i) printf("%c", st[i]);
    return 0;
}

View Code

bzoj3940censoring

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

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; 查看详情

bzoj3940[usaco2015feb]censoring*

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

bzoj3940

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

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

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

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

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

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

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

[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中找到最早出现的列表中的单词(... 查看详情

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在山脚。由于这座山处于高原内陆地区（... 查看详情

3940.[usaco15feb]censoringac自动机+栈(代码片段)

DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplenty ofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatest 查看详情

题解p3940分组(代码片段)

有些梦想虽然遥不可及，但不是不可能实现。只要我足够的强。前言调了挺长时间的，并查集合并的时候需要find一下，不然会炸内存。。。。解题思路参考了题解区一篇思路非常好的题解，在这里讲一下自己的见解。首先明确... 查看详情

hzwer的bzoj题单

counter:664BZOJ1601BZOJ1003BZOJ1002BZOJ1192BZOJ1303BZOJ1270BZOJ3039BZOJ1191BZOJ1059BZOJ1202BZOJ1051BZOJ1001BZOJ1588BZOJ1208BZOJ1491BZOJ1084BZOJ1295BZOJ3109BZOJ1085BZOJ1041BZOJ1087BZOJ3038BZOJ1821BZOJ1 查看详情

板刷bzoj计划（真香预警）

拒绝立(flag)总之寒假要以板刷(bzoj)第一页为目标，啥时候刷完不做硬性规定。。。bzoj1000A+BProblem太简单了，侮辱智商……bzoj1001bzoj1002bzoj1003bzoj1004bzoj1005bzoj1006bzoj1007bzoj1008bzoj1009bzoj1010 查看详情

踩着神犇的脚印走--hzwer刷题表inbzoj

如果ac了就有下划线咯。。。BZOJ1601 BZOJ1003BZOJ1002BZOJ1192BZOJ1303BZOJ1270BZOJ3039BZOJ1191BZOJ1059BZOJ1202BZOJ1051BZOJ1001BZOJ1588BZOJ1208BZOJ1491BZOJ1084BZOJ1295BZOJ3109BZOJ1085BZOJ1041BZOJ1087BZOJ3038BZOJ 查看详情

bzoj2212/bzoj3702

线段树合并nlogn.#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#definemaxn400500usingnamespacestd;intn,l[maxn],r[maxn],val[maxn],x,roots,root[maxn];intls[maxn 查看详情