正文 

当前位置： 首页 > 代码 > java教程

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

rorschach-xr rorschach-xr     2022-12-19     180

关键词：

题目描述

Farmer John has purchased a subscription to Good Hooveskeeping magazine for his cows, so they have plenty of material to read while waiting around in the barn during milking sessions. Unfortunately, the latest issue contains a rather inappropriate article on how to cook the perfect steak, which FJ would rather his cows not see (clearly, the magazine is in need of better editorial oversight).FJ has taken all of the text from the magazine to create the string S of length at most 10^5 characters. He has a list of censored words t_1 ... t_N that he wishes to delete from S. To do so Farmer John finds the earliest occurrence of a censored word in S (having the earliest start index) and removes that instance of the word from S. He then repeats the process again, deleting the earliest occurrence of a censored word from S, repeating until there are no more occurrences of censored words in S. Note that the deletion of one censored word might create a new occurrence of a censored word that didn‘t exist before.Farmer John notes that the censored words have the property that no censored word appears as a substring of another censored word. In particular this means the censored word with earliest index in S is uniquely defined.Please help FJ determine the final contents of S after censoring is complete.
FJ把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过10^5的字符串S。他有一个包含n个单词的列表，列表里的n个单词记为t_1...t_N。他希望从S中删除这些单词。 FJ每次在S中找到最早出现的列表中的单词(最早出现指该单词的开始位置最小)，然后从S中删除这个单词。他重复这个操作直到S中没有列表里的单词为止。注意删除一个单词后可能会导致S中出现另一个列表中的单词 FJ注意到列表中的单词不会出现一个单词是另一个单词子串的情况，这意味着每个列表中的单词在S中出现的开始位置是互不相同的 请帮助FJ完成这些操作并输出最后的S

输入

The first line will contain S. The second line will contain N, the number of censored words. The next N lines contain the strings t_1 ... t_N. Each string will contain lower-case alphabet characters (in the range a..z), and the combined lengths of all these strings will be at most 10^5.
第一行包含一个字符串S 
第二行包含一个整数N 
接下来的N行，每行包含一个字符串，第i行的字符串是t_i

输出

The string S after all deletions are complete. It is guaranteed that S will not become empty during the deletion process.
一行，输出操作后的S
 
 

多单词匹配显然ac自动机

照常建trie插入

用栈记录匹配字符时指针位置，如果匹配到单词就弹栈回到之前的状态

顺便记录修改后的串

之后直接输出答案

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct ac_auto

    struct node
    
        node *son[28],*fail;
        int size;
        node()
        
            memset(this,0,sizeof(node));
        
    ;
    node *root;
    void ini()
    
        root=new node();
    
    void ins(char *s)
    
        int l=strlen(s+1);
        node *now=root;
        for(int i=1;i<=l;i++)
        
            if(!now->son[s[i]-‘a‘])now->son[s[i]-‘a‘]=new node();
            now=now->son[s[i]-‘a‘];
        
        now->size=l;
    
    void build()
    
        queue<node*> q;
        for(int i=0;i<26;i++)
        
            if(root->son[i])
            
                q.push(root->son[i]);
                root->son[i]->fail=root;
            
            else root->son[i]=root;
        
        while(!q.empty())
        
            node *x=q.front();
            q.pop();
            for(int i=0;i<26;i++)
            
                if(x->son[i])
                
                    x->son[i]->fail=x->fail->son[i];
                    q.push(x->son[i]);
                
                else x->son[i]=x->fail->son[i];
            
        
    
    char ans[100005];int tot=0;
    node *st[100005];
    void query(char *s)
    
        node *now=root;
        st[0]=root;
        int l=strlen(s+1);
        for(int i=1;i<=l;i++)
        
            int x=s[i]-‘a‘;
            now=now->son[x];
            st[++tot]=now;
            ans[tot]=s[i];
            if(now->size)tot-=now->size,now=st[tot];
        
    
ac;
char S[100005],str[100005];
int n;
int main()

    scanf("%s%d",S+1,&n);
    ac.ini();
    for(int i=1;i<=n;i++)
        scanf("%s",str+1),ac.ins(str);
    ac.build();
    ac.query(S);
    for(int i=1;i<=ac.tot;i++)putchar(ac.ans[i]);
    return 0;

 

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

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

[bzoj3940][usaco2015feb]censoring

...内单词。保证不会出现二者包含状况。$nleq1e5,sumlenleq1e5$AC自动机裸题。build出AC自动机后从左到右插入文本串，同时边匹配边push进栈里。匹配成功就弹栈。注意要记录匹配到第几个字符的时候，AC自动机指针（我管那个一直蹦的... 查看详情

bzoj3940censoring

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

bzoj3940:[usaco2015feb]censoring

...把s中起始位置最早的一个模板串删掉，求最后剩的串。AC自动机，开个栈记一下每次走到哪里，匹配成功后直接在栈里找到这一串的初始位置对应自动机上的节点，从而回到刚才的样子就行了。1#include<stdio.h>2#include<string.h... 查看详情

censoring（bzoj3940）

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

bzoj3940[usaco2015feb]censoring

DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplentyofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatestissuecontain 查看详情

bzoj3940

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

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

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

...总分105我太菜了首先时间分配的不合理：第一题大水题ac自动机打完了都不会，第二题略微想了想打了个高斯消元，然后样例没过......，最后输出了一个随机数，第三题（lca板子忘了，打错一个地方，没有调出来）最后骗了五分&... 查看详情

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

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

[poj1625]censored!(ac自动机+dp+高精度)

 Censored!TimeLimit:5000MS MemoryLimit:10000KTotalSubmissions:10824 Accepted:2966DescriptionThealphabetofFreelandconsistsofexactlyNletters.EachsentenceofFreelandlanguage(alsoknownasFrei 查看详情

censoring——ac自动机(代码片段)

...2escapeexecution【样例输出】beginthatthebreakofdawn题解对于T建AC自动机，然后将$S$逐位压入栈中，跑AC自动机，当当前节点为$T_i$的结尾时，弹出即可代码1#inc 查看详情

bzoj1212l语言（ac自动机）

【BZOJ1212】L语言（AC自动机）题面BZOJ题解很自然的，既然要匹配单词，那就全部都丢到(AC)自动机里面去现在想想怎么匹配先是(AC)自动机正常的匹配如果此时这个位置能够匹配上一个串我们就需要判断一下这个串覆盖到这个文本... 查看详情

poj1625censored!（ac自动机+高精度+dp）

http://poj.org/problem?id=1625题意：给出一些单词，求长度为m的串不包含这些单词的个数。 思路：这道题和HDU2243和POJ2778是一样的，不同的是这道题不取模，所以不可以用矩阵快速幂，必须使用高精度，所以这里用滚动dp解决即可... 查看详情

bzoj2754喵星球上的点名（ac自动机）

【BZOJ2754】喵星球上的点名（AC自动机）题面BZOJ题解友情提示：此题请不要在cogs上提交，它的数据有毒对于点名串构建(AC)自动机然后把名字丢进去进行匹配，大力统计一下答案即可当然，要用(map)记录(trie)树#include<iostream>#in... 查看详情

bzoj1030文本生成器（ac自动机，动态规划）

【BZOJ1030】文本生成器（AC自动机，动态规划）题面BZOJ题解超级简单良心送分题很明显是所有状态-不合法状态合法状态就是(26^m)不合法状态做一个(dp)就好#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#inclu... 查看详情

bzoj3942[usaco2015feb]censoring*

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