首页 > 其他分享 >做题记录:P3121 [USACO15FEB] Censoring G

做题记录:P3121 [USACO15FEB] Censoring G

时间:2023-08-12 23:15:33浏览次数:45  
标签:head int void tot Censoring USACO15FEB MAXN P3121 now

题目传送门:click here

题意简化:给定一个文本串,和n个匹配串,删掉文本串中的匹配串求最后的字符串

做这题之前应该先做简化版:eazy mode

上面这题用kmp+栈就能过 以前如果用的是\(erase\)函数是错解,字符串的\(erase\)时间复杂度是常数级别的


看到这道题后非常的高兴,直接打了个爆力跳的板子丢了上去,然后就高高兴兴的TLE了

void ACquery(string s)
{
	l=0;
	int now=0;
	for(int i=0;i<s.size();i++)
	{
		now=tr[now][s[i]-'a'+1];
		q[++l]=i;
		f[i]=now;
		int t=now;
		while(t)
		{
			if(end[t]) 
			{
				l-=len[t];
				now=f[q[l]];
				break;
			}
			t=fail[t];
		}
	}
}

回过头想一想,往上跳是\(O(|T|)\)的,跳\(|S|\)次时间直接\(O(|T||S|)\)飞天的时间复杂度

那咋办?

看看\(while\)其实是可以优化的,往上跳到第一个有权值的点

不妨想一想我们在做AC自动机板子的时候是怎么优化的

不也就是建一颗失配树然后\(dfs\)一遍嘛

这也是这样,往上找第一个有权值的祖先预处理就彳亍了

Code:

void dfs(int now,int v)
{
	if(end[now]) v=now;
	last[now]=v;
	for(int i=head[now];i;i=e[i].next)
	{
		int son=e[i].to;
		dfs(son,v);
	}
}

这样就优化成\(O(|S|+|T|)\)咯

AC Code:

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n,f[MAXN];
int q[MAXN],l,r;
int tr[MAXN][28],fail[MAXN],end[MAXN],len[MAXN],cnt;
int last[MAXN];
string str,s;
int head[MAXN],tot=1;
struct edge{
	int to,next;
}e[MAXN];
void add(int u,int v)
{
	e[tot].to=v;
	e[tot].next=head[u];
	head[u]=tot++;
}
void insert(string s)
{
	int now=0;
	for(int i=0;i<s.size();i++)
	{
		int c=s[i]-'a'+1;
		if(!tr[now][c]) tr[now][c]=++cnt,len[cnt]=len[now]+1;
		now=tr[now][c];
	}
	end[now]++;
}
void getfail()
{
	for(int i=1;i<=26;i++)
		if(tr[0][i]) q[++r]=tr[0][i];
	while(l<r)
	{
		int now=q[++l];
		for(int i=1;i<=26;i++)
		if(tr[now][i])
		{
			fail[tr[now][i]]=tr[fail[now]][i];
			q[++r]=tr[now][i];
		}
		else tr[now][i]=tr[fail[now]][i];
	}
}
void ACquery(string s)
{
	l=0;
	int now=0;
	for(int i=0;i<s.size();i++)
	{
		now=tr[now][s[i]-'a'+1];
		q[++l]=i;
		f[i]=now;
		int t=now;
		if(last[t]!=-1)
		{
			l-=len[last[t]];
			now=f[q[l]];
		}
	}
}
void dfs(int now,int v)
{
	if(end[now]) v=now;
	last[now]=v;
	for(int i=head[now];i;i=e[i].next)
	{
		int son=e[i].to;
		dfs(son,v);
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>str>>n;
	for(int i=1;i<=n;i++)
		cin>>s,insert(s);
	getfail();
	for(int i=1;i<=cnt;i++)
		add(fail[i],i);
	dfs(0,-1);
	ACquery(str);
	for(int i=1;i<=l;i++)
		cout<<str[q[i]];
	return 0;
}

标签:head,int,void,tot,Censoring,USACO15FEB,MAXN,P3121,now
From: https://www.cnblogs.com/g1ove/p/17625797.html

相关文章

  • P4826 [USACO15FEB] Superbull S题解
    SuperbullS题解题目传送门(可点击)题面题目描述\(Bessie\)和她的朋友们正在一年一度的\(Superbull\)锦标赛中打球,而\(Farmer\)\(John\)负责让比赛尽可能激动人心。总共有N支队伍(\(1\leN\le2000\))参加了\(Superbull\)锦标赛。每个团队都有一个\(1...2^{30}−1\)的团队ID......
  • BZOJ 3942: [Usaco2015 Feb]Censoring KMP
    3942:[Usaco2015Feb]CensoringTimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 476  Solved: 260[Submit][Status][Discuss]DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplentyofmateria......
  • Luogu P4824 [USACO15FEB] Censoring S
    [USACO15FEB]CensoringS题面翻译FarmerJohn为他的奶牛们订阅了GoodHooveskeeping杂志,因此他们在谷仓等待挤奶期间,可以有足够的文章可供阅读。不幸的是,最新一期的文章包含一篇关于如何烹制完美牛排的不恰当的文章,FJ不愿让他的奶牛们看到这些内容。FJ已经根据杂志的所有文字,......
  • COMP3121/9101 23T1难点分析
    COMP3121/910123T1—Assignment2(UNSWSydney)DueMonday27thMarchat5pmSydneytimeInthisassignmentweapplythegreedymethodandassociatedgraphalgo......
  • P4824 [USACO15FEB] Censoring S
    希望在Str中删掉1个屏蔽词(一个屏蔽词可能出现多次)求最后的串 栈+hash #include<iostream>#include<cstring>usingnamespacestd;constintN=1e6+3;......
  • 关于AC自动机的一些理解 || Luogu3121 & 4824 Censoring - 哈希 - AC自动机
    题目链接:https://www.luogu.com.cn/problem/P3121(4824)题解:4824是CensoringS,只需要对单模式串进行操作,3121需要对多模式串4824开一个前缀hash数组,每次扫到当前点......
  • P4826 [USACO15FEB]Superbull S
    最大生成树,暴力加贪心;#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongull;constintN=2007;ullid[N];intf[N];structNode{ inti,j;......
  • luoguP4824 [USACO15FEB] Censoring S 解题报告
    血的教训。。。传送门题意FJ已经根据杂志的所有文字,创建了一个字符串$S$($S$的长度保证不超过$10^6$),他想删除其中的子串$T$,他将删去$S$......
  • P3120 [USACO15FEB]Cow Hopscotch G
    传送门思路朴素的想法就是一个\(O(n^2m^2)\)的转移:\[f_{i,j}=\sum_{x=1}^{i-1}\sum_{y=1}^{j-1}f_{x,y}*[a_{i,j}!=a_{x,y}]\]约束条件如此多,思考用cdq分治来优化......