差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:hotpot:ac自动机 [2020/08/21 17:39]
lotk
+++ 2020-2021:teams:hotpot:ac自动机 [2020/08/26 15:44] (当前版本)
lotk
@@ 行 82: / 行 82: @@
 		for(int i=0;i<26;++i)
 			if(ch[x][i]){
-				if(x)fail[ch[x][i]]=ch[fail[x]][i];
+				if(x){
+					fail[ch[x][i]]=ch[fail[x]][i];
+					if(Count[ch[fail[x]][i]])nxt[ch[x][i]]=ch[fail[x]][i];
+					else nxt[ch[x][i]]=nxt[ch[fail[x]][i]];
+				}
 				Q.push(ch[x][i]);
-				if(Count[ch[fail[x]][i]])nxt[ch[x][i]]=ch[fail[x]][i];
-				else nxt[ch[x][i]]=nxt[ch[fail[x]][i]];
 			}
 			else ch[x][i]=ch[fail[x]][i];
@@ 行 116: / 行 118: @@
 }
+</code>
+[[https://www.luogu.com.cn/problem/P3796|P3796 【模板】AC自动机（加强版）]]
+ps:本题按输入顺序输出所有出现次数最多的模式串。保留所有的串编号最后排序输出即可。
+<code cpp>
+#include<algorithm>
+#include<stack>
+#include<ctime>
+#include<cstring>
+#include<cmath>
+#include<iostream>
+#include<iomanip>
+#include<cstdio>
+#include<queue>
+using namespace std;
+inline int read(){
+	int num=0,f=1;char x=getchar();
+	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
+	while(x>='0'&&x<='9'){num=num*10+x-'0';x=getchar();}
+	return num*f;
+}
+const int maxn=75*155;
+char s[1000005];
+bool str[maxn];
+int ch[maxn][26],cnt,fail[maxn];
+int prt[maxn],nxt[maxn];
+int uni[maxn];
+char alp[maxn];
+int n;
+void Insert(int bh){
+	scanf("%s",s);
+	int len=strlen(s);
+	int x=0;
+	for(int i=0;i<len;++i){
+		int t=s[i]-'a';
+		if(!ch[x][t]){
+			ch[x][t]=++cnt;
+			prt[cnt]=x;alp[cnt]=s[i];
+		}
+		x=ch[x][t];
+	}
+	str[x]=true;uni[x]=bh;
+}
+queue<int> Q;
+void build_ac(){
+	Q.push(0);
+	while(Q.size()){
+		int x=Q.front();Q.pop();
+		for(int i=0;i<26;++i)
+			if(ch[x][i]){
+				if(x){
+					fail[ch[x][i]]=ch[fail[x]][i];
+					if(str[ch[fail[x]][i]])nxt[ch[x][i]]=ch[fail[x]][i];
+					else nxt[ch[x][i]]=nxt[ch[fail[x]][i]];
+				}
+				Q.push(ch[x][i]);
+			}else ch[x][i]=ch[fail[x]][i];
+	}
+}
+typedef pair<int,int> pr;
+vector<pr> ans;
+int MAX,num[maxn];
+void qans(){
+	scanf("%s",s);
+	int len=strlen(s);
+	int x=0;
+	for(int i=0;i<len;++i){
+		int t=s[i]-'a';
+		int nw=ch[x][t];
+		while(nw){
+			if(str[nw])++num[nw];
+			if(num[nw]==MAX)ans.push_back(pr(uni[nw],nw));
+			if(num[nw]>MAX){
+				MAX=num[nw];ans.clear();
+				ans.push_back(pr(uni[nw],nw));
+			}
+			nw=nxt[nw];
+		}
+		x=ch[x][t];
+	}
+}
+void write(int x){
+	if(!x)return;
+	write(prt[x]);
+	printf("%c",alp[x]);
+}
+void Print(){
+	printf("%d\n",MAX);
+	sort(ans.begin(),ans.end());
+	for(auto x:ans){
+		write(x.second);
+		puts("");
+	}
+}
+void clear(){
+	MAX=cnt=0;
+	memset(str,0,sizeof str);
+	memset(ch,0,sizeof ch);
+	memset(fail,0,sizeof fail);
+	memset(nxt,0,sizeof nxt);
+	memset(num,0,sizeof num);
+	memset(prt,0,sizeof prt);
+	ans.clear();
+}
+int main(){
+	while(true){
+		clear();
+		n=read();
+		if(!n)break;
+		for(int i=1;i<=n;++i)Insert(i);
+		build_ac();
+		//cout<<'a'<<endl;
+		qans();
+		Print();
+	}
+	return 0;
+}
 </code>
+[[https://www.luogu.com.cn/problem/P5357|P5357 【模板】AC自动机（二次加强版）]]
+ps:本题方法基本同上，记录一下每个串在trie上对应的点就可以了。
+<code cpp>
+#include<algorithm>
+#include<stack>
+#include<ctime>
+#include<cstring>
+#include<cmath>
+#include<iostream>
+#include<iomanip>
+#include<cstdio>
+#include<queue>
+using namespace std;
+inline int read(){
+	int num=0,f=1;char x=getchar();
+	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
+	while(x>='0'&&x<='9'){num=num*10+x-'0';x=getchar();}
+	return num*f;
+}
+const int maxn=200005;
+char s[maxn*10];
+bool str[maxn];
+int ch[maxn][26],cnt,fail[maxn];
+int nxt[maxn],uni[maxn];
+int n;
+void Insert(int bh){
+	scanf("%s",s);
+	int len=strlen(s);
+	int x=0;
+	for(int i=0;i<len;++i){
+		int t=s[i]-'a';
+		if(!ch[x][t])ch[x][t]=++cnt;
+		x=ch[x][t];
+	}
+	str[x]=true;uni[bh]=x;
+}
+queue<int> Q;
+void build_ac(){
+	Q.push(0);
+	while(Q.size()){
+		int x=Q.front();Q.pop();
+		for(int i=0;i<26;++i)
+			if(ch[x][i]){
+				if(x){
+					fail[ch[x][i]]=ch[fail[x]][i];
+					if(str[ch[fail[x]][i]])nxt[ch[x][i]]=ch[fail[x]][i];
+					else nxt[ch[x][i]]=nxt[ch[fail[x]][i]];
+				}
+				Q.push(ch[x][i]);
+			}else ch[x][i]=ch[fail[x]][i];
+	}
+}
+int num[maxn];
+void qans(){
+	scanf("%s",s);
+	int len=strlen(s);
+	int x=0;
+	for(int i=0;i<len;++i){
+		int t=s[i]-'a';
+		int nw=ch[x][t];
+		while(nw){
+			if(str[nw])++num[nw];
+			nw=nxt[nw];
+		}
+		x=ch[x][t];
+	}
+}
+int main(){
+	n=read();
+	for(int i=1;i<=n;++i)Insert(i);
+	build_ac();
+	qans();
+	for(int i=1;i<=n;++i)printf("%d\n",num[uni[i]]);
+	return 0;
+}
+</code>

CVBB ACM Team

用户工具

站点工具

差别

页面工具