AC 自动机是 以 Trie 的结构为基础 ，结合 KMP 的思想 建立的。

文章目录

解决：多模式匹配问题

匹配问题：
有多个不同的模式串s[1…N]
给定长度=M的目标串t，求每个模式串s[i]总共在t中出现了多少次
跑N遍kmp

字典树：

对所有的模式串s[1…N]构建trie
字典树的根到字典树上任意节点构成的路径都对应某个模式串s[i]的前缀
概念：
状态：对字典树的任何一个结点都看做状态，对应某个模式串s[i]的前缀
转移：任意一个状态添加一个字符得到新状态
可识别：字符串能对应上字典树上的一个状态

"the"为可识别状态

int tot=∑|s|;
struct Node{
   
	int id;//s[id]结尾 
	Node *nxt[26];
}pool[tot],*rt;
void insert(string s,int id){
   
	Node *p=rt;
	int c;
	for(int i=0;i<s.length();i++)
	{
   
		c=s[i]-'0';
		if(p->nxt[c]==NULL)p->next[c]=pool+(++top);
		p=p->nxt[c];
		if(i==s.length()-1)p->id=id;
	}
}

Fail指针

AC自动机利用一个fail指针来辅助多模式串的匹配
状态u的fail指针指向另一个可识别状态v，且v是u的最长后缀，即fail[u] = 状态u的最长可识别后缀

求fail[u]指针

图中红色线为fail指针所指

所谓border，就是next[len(β)]，直观含义是除了串本身以外，使得前缀等于后缀的最长的一段前缀。
类比求next[j] = pre(s,j)的最长border
pre(s,j-1)的所有border长度为k1 = next[j-1], k2=next[next[j-1]]…
需要找到最大的k使得s[k+1] = s[j] 成立了
此时next[j] = k+1

现在我们来看fail，字典树当前的状态为p，p添加字符c的边（记为p->c）指向状态u，即p->c=u。并假设深度小于u的所以结点的fail指针都已求得
p的所有可识别后缀：k1=fail[p], k2=fail[fail[p]],…
找到其中深度最大的状态k使得k->c 可识别（存在）
此时fail[u]= k->c

如果fail[p]->c存在：则让fail[u]=fail[p]->c.相当于在p和fail[p]后面加一个字符c，分别对应u和fail[u]
如果fail[p]->c不存在：那么继续检查fail[fail[p]]->c，一直跳fail指针直到根节点，如果真没有，那就fail[u]=rt，指向根节点

代码：

void bulid()
{
   
	queue<Node*>q;
	rt->fail=rt;
	for(int k=0;k<26;k++)
	{
   
		if(rt->nxt[k])q.push(rt->nxt[k]);
		else rt->nxt[k]=rt;
		rt->nxt[k]->fail=rt;
	}
	//bfs
	while(!q.empty())
	{
   
		Node *p=q.front();
		q.pop();
		for(int k=0;k<26;k++)
		{
   
			if(p->nxt[k])//如果有孩子 
			{
   
				p->nxt[k]->fail=p->fail->nxt[k];
				q.push(p->nxt[k]);
			}
			else p->nxt[k]=p->fail->nxt[k];//如果没有孩子，（相当于路径压缩） ，图中的黑线部分
		}
	}
}

void build() {
   
  for (int i = 0; i < 26; i++)
    if (tr[0][i]) q.push(tr[0][i]);
  while (q.size()) {
   
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
   
      if (tr[u][i])
        fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
      else
        tr[u][i] = tr[fail[u]][i];
    }
  }
}


最终形态：

多模式匹配

  1. 建trie O(∑|S|)
  2. 求所有状态的fail指针
    fail已经没有空指针，所以在图上大胆走

    黄色为模式串
    问模式串在t中出现几次？
    直接计算模式串上有几个i不可，虽然01,010,11都是正确的（01上i出现了四次，i=2,4，5,8），但是1却不对，1上一个i也没有，但是1在t中五次
    暴力向上跳fail，一直跳到rt，该路径上的串均为出现
    到01时，跳fail到1，又到rt，01和1均出现一次
    也就是，fail链上所有模式串都加一

代码：

int query(char *t) {
   
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
   
    u = tr[u][t[i] - 'a'];  // 转移
    for (int j = u; j && e[j] != -1; j = fail[j]) {
   
      res += e[j], e[j] = -1;
    }
  }
  return res;
}

但是！！复杂度太高了
会被卡，
正确做法是建fail树
每个点u认fail[u]为爸爸（有点像并查集的形式）
（黄色为模式串）

我们能发现下列特征：
1.u->rt : 链+1
2.单点求值
3.离线操作
可以用树上差分，复杂度 O（节点个数∑|S|）


模式串1的出现次数 = 子树内所有1求和 = 5
AC自动机：总复杂度：O(∑|S|+26*∑|S|+|t|)

总代码：

#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
int N,Q;
struct Node{
   
	int cnt;
	Node *nxt[26];
	Node* fail;
	vector<Node*>adj;
}*rt; 
int top=0;
Node pool[MAXN];
Node* pos[MAXN];
void insert(string s,int x){
   
	Node *p=rt;
	int id;
	for(int i=0;i<s.length();i++)
	{
   
		id=s[i]-'a';
		if(p->nxt[id]==NULL)p->nxt[id]=pool+(++top);
		p=p->nxt[id];
		if(i==s.length()-1)pos[x]=p;
	}
}
void bulid()
{
   
	queue<Node*>q;
	rt->fail=rt;
	for(int k=0;k<26;k++)
	{
   
		if(rt->nxt[k])
		{
   
			rt->adj.push_back(rt->nxt[k]);
			q.push(rt->nxt[k]);
		}
		else rt->nxt[k]=rt;
		
		rt->nxt[k]->fail=rt;
	}
	
	while(!q.empty())
	{
   
		Node *p=q.front();
		q.pop();
		for(int k=0;k<26;k++)
		{
   
			if(p->nxt[k])//如果有孩子 
			{
   
				p->nxt[k]->fail=p->fail->nxt[k];
				p->fail->nxt[k]->adj.push_back(p->nxt[k]);
				q.push(p->nxt[k]);
			}
			else p->nxt[k]=p->fail->nxt[k];//如果没有孩子，（相当于路径压缩） ，图中的黑线部分
		}
	}
}
string s,t;
void dfs(Node* p)
{
   
	for(int k=0;k<p->adj.size();k++)
	{
   
		dfs(p->adj[k]);
		p->cnt+=p->adj[k]->cnt;
	}
}
int main()
{
   
	ios::sync_with_stdio(false);
	cin>>N;
	rt=pool;
	for(int i=1;i<=N;i++)
	{
   
		cin>>s;
		insert(s,i);
	}
	bulid();
	cin>>t;
	Node *p=rt;
	for(int i=0;i<t.length();i++)
	{
   
		p=p->nxt[t[i]-'a'];
		++(p->cnt);
	}
	dfs(rt);
	for(int i=1;i<=N;i++)
	{
   
		cout<<pos[i]->cnt<<endl;
	}
	return 0;
}