AC自动机可以解决多个模式串匹配一个主串的情况，不需要将每个字串用KMP匹配一次，换时间……
首先把模式串建一个Trie图，然后在Trie图里面找当前节点的最长后缀，比KMP多考虑了其他串。
显然Trie树中下面的节点比上面的节点表示的串更长，于是优先考虑同层的，然后向上考虑……
然后可以像KMP那样按照bfs递推了……
图上画了几个失配指针，其实除了根结点的每个节点都有失配指针
失配是指某个节点之后没有对应的节点，这时候沿着失配指针往回走后再判断是否失配
类似于KMP，设$f[v]$为节点$v$的失配指针，于是就可以得到以下递推关系
若存在$v.son==f^x[v].son$，则$f[v.son]$=$f[f^x[v].son]$
代码如下：
int trie[MAXN][26], e[MAXN], cnt; int c[157],f[MAXN],lst[MAXN]; inline void init() { memset(trie,0,sizeof trie); memset(e,0,sizeof e); //表示以这个节点结尾的模式串编号（从1开始） cnt=0; //Trie树大小 memset(c,0,sizeof c); mp.clear(); } inline void addt(char *t, int k) { //添加进Trie树 int l=strlen(t); int f=0; REP(i,0,l) { int &c=trie[f][t[i]-'a']; if(!c) { c=++cnt; } f=c; } e[f]=k; } inline void getf() { queue<int> q; f[0]=0; REP(i,0,26) { int k=trie[0][i]; if(k) { q.push(k);lst[k]=0, f[k]=0; } } while(!q.empty()) { int t=q.front(); q.pop(); REP(i,0,26) { int k=trie[t][i]; if(!k) { // 为了搜索时不再使用失配指针，将不存在的节点直接改成失配指针 trie[t][i]=trie[f[t]][i]; continue; } q.push(k); int v=f[t]; // 肯定不能自己的son指向自己的son，如果等于t，那么下一步循环就没意义了 while(v && !trie[v][i]) v=f[v]; // 直到t.son==f^x [t].son f[k]=trie[v][i]; // 则f[t.son]=f[f^x [t].son] lst[k]=e[f[k]]?f[k]:lst[f[k]]; // 数学归纳法，指向沿着失配指针到的单词节点 或者根结点 } } } inline void addcnt(int f) { // 找到一个模式串后的操作，使用迭代防止递归拖时间（虽然O2可以优化……） while(f) { c[e[f]]++; f=lst[f]; // 当前节点的某个后缀是模式串结尾 } } inline void calc(char *s) { // 寻找所有模式串 int l=strlen(s); int f=0; REP(i,0,l) { f=trie[f][s[i]-'a']; // 直接沿着trie，找不到会自动走失配指针 if(e[f]) addcnt(f); // 当前节点是模式串结尾 else if(lst[f]) addcnt(lst[f]);// 当前节点的某个后缀是模式串结尾 } }
没有总结模板……
转载于:https://www.cnblogs.com/sahdsg/p/10930181.html
相关资源：中文高性能AC自动机代码