差别

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

--- 2020-2021:teams:hotpot:ac自动机 [2020/08/21 17:02]
lotk
+++ 2020-2021:teams:hotpot:ac自动机 [2020/08/26 15:44] (当前版本)
lotk
@@ 行 35: / 行 35: @@
 后缀链接可以在失配指针之后求出，如果 $fail(i)$ 为单词结点，则 $nxt(i)=fail(i)$,否则 $nxt(i)=nxt(fail(i))$
+====优化====
+由于每次失配时需要用到失配指针，每次加入字符时经过节点数不确定，复杂度可能退化，但对于一个状态，添加一个字符后，转移到的状态是确定的，这也意味着我们可以预处理每一个状态可能装一道的所有状态。
+对于节点 $i$ ,如果它有字符 $c$的出边,则加入 $c$ 时，它可以直接转移到该边指向结点，否则应该转移到fail(i)加入对应字符转移到的点上，我们可以用递推的方式求出这些转移方式，加入这些边，得到$Trie$图
+====模板题====
+[[https://www.luogu.com.cn/problem/P3808|P3808 【模板】AC自动机（简单版）]]
+ps:本题由于只记录串出现次数，可以通过标记来优化复杂度。
+<code cpp>
+#include<iostream>
+#include<iomanip>
+#include<cstdio>
+#include<algorithm>
+#include<map>
+#include<stack>
+#include<queue>
+#include<complex>
+#include<cmath>
+#include<cstring>
+using namespace std;
+const int maxn=1000005;
+char s[maxn];
+int cnt,ch[maxn][26],Count[maxn],fail[maxn];
+int nxt[maxn];
+void Insert(){
+	scanf("%s",s+1);
+	int len=strlen(s+1);
+	int rt=0;
+	for(int i=1;i<=len;++i){
+		int t=s[i]-'a';
+		if(!ch[rt][t])ch[rt][t]=++cnt;
+		rt=ch[rt][t];
+	}
+	++Count[rt];
+}
+queue<int> Q;
+void Build_AC(){
+	Q.push(0);
+	while(!Q.empty()){
+		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(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]);
+			}
+			else ch[x][i]=ch[fail[x]][i];
+	}
+}
+void Query(){
+	scanf("%s",s+1);
+	int len=strlen(s+1),rt=0;
+	int ans=0;
+	for(int i=1;i<=len;++i){
+		int t=s[i]-'a';
+		int a=ch[rt][t];
+		while(a){
+			if(Count[a]==-1)break;
+			ans+=Count[a];
+			Count[a]=-1;
+			a=nxt[a];
+		}
+		rt=ch[rt][t];
+	}
+	printf("%d",ans);
+}
+int n;
+int main(){
+	scanf("%d",&n);
+	for(int i=1;i<=n;++i)Insert();
+	Build_AC();
+	Query();
+	return 0;
+}
+</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

用户工具

站点工具

差别

页面工具