AC自动机总结

如果你还不知道KMP是什么，或者不知道Trie是什么，先点下面的链接，学好这两样再来看这篇文章。

KMP入门教程传送门。

Trie入门教程传送门。

好，那么我来讲讲AC自动机吧。

以洛谷P3808模板题为例，

如果我们有n个模式串，和一个文本串，我们需要统计有多少个模式串在文本串中出现了，怎么办？

显然，如果我们直接枚举每个模式串，然后将其与文本串进行匹配，判断是否匹配成功，那么效率就是O(n*length(T))，很不理想。

那么我们是否有什么可以利用的信息呢？

如2个模式串：hers，he，显然如果我们匹配到了一个hers，就一定会有一个he。那么我们有一个新的优化思路，先将n个模式串两两匹配，确定包含关系，然后再在文本串里匹配，显然这个思路的效率最坏情况下可以达到O(n^2+n*length(T))，更差。

那为什么要提它呢？

因为这个包含关系我们可以优化！我们根本无需两两匹配，我们直接把n个模式串建成一个Trie，然后用一个bfs直接计算包含关系就好了！这个bfs的效率是O(sigma_length(S))~=O(length(T))的。

那么剩下的工作就好办了，我们直接枚举文本串的每一位，然后用Trie进行O(1)递推的查找与当前文本串结尾相同的模式串就行了。（这句话可能并太好懂，也可以这样解释：由前几位的字符和当前位的字符，我们可以在Trie中确定唯一一个节点，具体的可以参见代码）

可是有的人也许就会问，这个包含关系有什么用，也许n个模式串根本就两两毫不包含呢？

确实，包含这种说法并不准确。其实我们就是在计算失配函数，

只是这个失配函数非常的特殊，因为它是建在一个Trie上的。

我们重新定义KMP中的失配函数。

设f[u]=v表示从根到u号节点的这个字符串的某个后缀与从根到v号节点的这个字符串是等效的（即完全相等的）！这个后缀必须是尽量地长。

我们匹配到在一个模式串的时候就不断的沿着失配边跳，所有的端点v是标记点的失配边都对应了一个模式串。

但是这个失配关系往往会非常复杂，即我们跳了很多次，但是没有一个端点是标记点，所以我们引入last指针的优化。

即定义last[u]=v表示从u开始不断沿着失配边跳到的第一个是标记点的端点v，那么我们再匹配是就无需沿着f跳，而是沿着last跳，每跳到一个last，它就一定对应一个模式串，所以效率是非常高的。

我们首先考虑f的递推。我们设当前节点为u，其一个孩子ch[u][c]=v，k表示u沿着f边跳一次对应的点，即k=f[u],

那么如果u不是根节点，f[v]=ch[k][c]，即沿着k再向下走一个c字符，这时两个字符串还是相等的对不对。

如果u是根节点那就没什么好说的了，f[v]=0。

在此条件下，last就非常好递推了，,那么如果f[v]是标记点，那么last[v]=f[v],

否则last[v]=last[f[v]]。

这个f[v]并不能保证ch[k][c]就一定存在，所以还需要一个while循环一直跳直到找到一个ch[k][c]!=0的端点。可以出现了一个while，既使代码不够优美，又使效率无法保证，所以我们直接把所有ch[k][c]=0的端点的ch[k][c]直接连向ch[f[k]][c]，就好像并差集的一个路径压缩，由于Trie是读完所有模式串后建的，所以这个加边并不会影响Trie。

考虑到这是一个Trie树上的递推，所以我们用BFS搞一搞就好了。

效率显而易见O(sigma_length(S)+length(T))

和Trie一样，AC自动机的裸题并不多见，常常是和DP结合坑人。

而AC自动机的裸题，先把模板打好后，基本上改的就是对标记点的处理。

P3808：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define REP(i,a,b) for (int i=(a);i<=(b);i++)
#define reset(a) memset((a),0,sizeof((a)))
using namespace std;
const int N=1e6+10;
char P[N];
int n;
struct Aho_Corasick_Automaton{
	int ch[N][26],val[N],f[N],last[N],NodeCnt;
	void clear(){
		reset(ch);reset(val);reset(f);reset(last);
		NodeCnt=0;
	}
	void insert(char *S){
		int u=0,n=strlen(S);
		REP(i,0,n-1){
			int c=S[i]-'a';
			if (!ch[u][c])ch[u][c]=++NodeCnt;
			u=ch[u][c];
		}
		val[u]++;
	}
	void getFail(){
		queue<int> Q;
		Q.push(0);
		while (!Q.empty()){
			int u=Q.front(),k=f[u];Q.pop();
			REP(c,0,25){
				int v=ch[u][c];
				if (!v){ch[u][c]=ch[k][c];continue;}
				Q.push(v);
				f[v]=u?ch[k][c]:0;
				last[v]=val[f[v]]?f[v]:last[f[v]];
			}
		}
	}
	int count(char *T){
		int u=0,n=strlen(T),res=0;
		REP(i,0,n-1){
			int c=T[i]-'a';
			u=ch[u][c];
			if (val[u])res+=val[u],val[u]=0;
			int v=u;
			while (last[v]){
				v=last[v];
				if (val[v])res+=val[v],val[v]=0;
			}
		}
		return res;
	}
}AC;
int main(){
	scanf("%d",&n);
	AC.clear();
	REP(i,1,n){
		scanf("%s",P);
		AC.insert(P);
	}
	AC.getFail();
	scanf("%s",P);
	printf("%d\n",AC.count(P));
	return 0;
}

洛谷P3796：

就是对AC自动标记点处理的简单修改，即把匹配到的标记点都计数一下，然后求计数最大的那些标记点就行了。

参考代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define reset(a) memset((a),0,sizeof((a)))
#define REP(i,a,b) for (int i=(a);i<=(b);i++)
using namespace std;
const int N=1e6+10;
const int M=151*71;
char s[151][71];
char T[N];
int m;
struct Aho_Corasick_Automaton{
	int NodeCnt,f[M],ch[M][26],cnt[M],val[M],last[M];
	void clear(){
		reset(f);reset(ch);reset(cnt);reset(val);reset(last);
		NodeCnt=0;
	}
	void insert(char *s,int index){
		int u=0,n=strlen(s);
		REP(i,0,n-1){
			int c=s[i]-'a';
			if (!ch[u][c])ch[u][c]=++NodeCnt;
			u=ch[u][c];
		}
		val[u]=index;
	}
	void getFail(){
		queue<int> Q;
		Q.push(0);
		while (!Q.empty()){
			int u=Q.front(),k=f[u];Q.pop();
			REP(c,0,25){
				int v=ch[u][c];
				if (!v){ch[u][c]=ch[k][c];continue;}
				f[v]=u?ch[k][c]:0;
				last[v]=val[f[v]]?f[v]:last[f[v]];
				Q.push(v);
			}
		}
	}
	void query(char *T){
		int u=0,n=strlen(T),res=0;
		REP(i,0,n-1){
			int c=T[i]-'a';
			u=ch[u][c];
			if (val[u])cnt[val[u]]++;
			int v=last[u];
			while (v){
				if (val[v])cnt[val[v]]++;
				v=last[v];
			}
		}
		REP(i,1,m)res=max(res,cnt[i]);
		printf("%d\n",res);
		REP(i,1,m)if (cnt[i]==res)printf("%s\n",s[i]);
		return;
	}
}AC;
int main(){
	while (scanf("%d",&m)==1 && m){
		AC.clear();
		REP(i,1,m){
			scanf("%s",s[i]);
			AC.insert(s[i],i);
		}
		AC.getFail();
		scanf("%s",T);
		AC.query(T);
	}
	return 0;
}