2021.11.09 P4824 [USACO15FEB]Censoring S与P3121 [USACO15FEB]Censoring G（KMP&&AC自动机）

2021.11.09 P4824 [USACO15FEB]Censoring S与P3121 [USACO15FEB]Censoring G（KMP&&AC自动机）

https://www.luogu.com.cn/problem/P4824

题意：

给定字符串S和T，删除S中的T，形成新串，继续删除新串中的T，直至完全删除。

分析：

KMP求的是当前S的第i位能匹配到T的第j位，如果j==strlen(T)删除stacki中i-strlen(T)+1~i，继续从S的i+1、k=f[stacki[top]]与T开始继续匹配。

代码如下：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e6+10;

int nexti[N],f[N],stacki[N],top;

char s[N],t[N];

inline void getnext(char *s){

	int n=strlen(s);

	int k=-1;nexti[0]=-1;

	for(int i=0;i<n;){

		while(s[i]!=s[k]&&k!=-1)k=nexti[k];

		if(s[i]==s[k]||k==-1)nexti[++i]=++k;

	}

}

int main(){

	//freopen("P4824.out","w",stdout);

	scanf("%s",s);

	scanf("%s",t);

	getnext(t);

	//for(int i=1;i<=strlen(t);i++)cout<<nexti[i]<<" ";cout<<endl<<endl;

	int k=0,n=strlen(s),m=strlen(t);

	for(int i=0;i<=n;i++){

		while(s[i]!=t[k]&&k!=-1)k=nexti[k];

		if(s[i]==t[k]||k==-1)f[i]=++k;

		stacki[++top]=i;

		//cout<<top<<endl;

		//for(int j=1;j<=top;j++)cout<<s[stacki[j]]<<" ";cout<<endl;

		if(k==m)top-=m,k=f[stacki[top]];

		//cout<<top<<endl;

		//for(int j=1;j<=top;j++)cout<<s[stacki[j]];cout<<endl;//     <<endl;

	}

	//for(int i=1;i<=strlen(s);i++)cout<<f[i]<<" ";cout<<endl;

	for(int i=1;i<=top;i++)cout<<s[stacki[i]];

	return 0;

}

https://www.luogu.com.cn/problem/P3121

题意：

给定字符串S和若干个T，删除S中的存在的T，形成新串，继续删除新串中存在的T，直至完全删除。

分析：

如上，只不过一对多需要用AC自动机，继续使用手工栈辅助。

代码如下：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<queue>

#include<algorithm>

using namespace std;

const int N=1e5+10;

int m,top,stacki[N],f[N];

char s[N],t[N];

namespace trie{

	int t[N][30],tot,val[N],fail[N];

	queue<int>q;

	void insert(char *s){

		int len=strlen(s),u=0;

		for(int i=0;i<len;i++){

			int v=s[i]-'a';

			if(!t[u][v])t[u][v]=++tot;

			u=t[u][v];

		}

		val[u]=len;

	}

	void build(){

		for(int i=0;i<26;i++)if(t[0][i])q.push(t[0][i]);

		while(!q.empty()){

			int u=q.front();q.pop();

			for(int i=0;i<26;i++){

				if(t[u][i])fail[t[u][i]]=t[fail[u]][i],q.push(t[u][i]);

				else t[u][i]=t[fail[u]][i];

			}

		}

	}

};

int main(){

	scanf("%s",s);

	cin>>m;

	for(int i=1;i<=m;i++)scanf("%s",t),trie::insert(t);

	trie::build();

	int len=strlen(s),u=0;

	for(int i=0;i<len;i++){

		int v=s[i]-'a';

		f[i]=u=trie::t[u][v];

		stacki[++top]=i;

		if(trie::val[u]){

			top-=trie::val[u];

			u=f[stacki[top]];

		}

	}

	for(int i=1;i<=top;i++)cout<<s[stacki[i]];

	return 0;

}

2021.11.09 P4824 [USACO15FEB]Censoring S与P3121 [USACO15FEB]Censoring G（KMP&&AC自动机）的相关教程结束。