一.前言

想学AC自动机，请先学会KMP和Trie树。

二.正文

AC自动机到底是什么呢？\(Trie+KMP\)

我们的AC自动机和KMP有什么区别呢?

AC自动机可以同时匹配很多个模式串，而KMP只可以匹配一个模式串。

那么我们来看一道例题:传送门

我们可以想到对于每一个字符串进行一次KMP，然鹅会TLE。

AC自动机就是一个算法，它可以同时进行多次KMP。

我们举一个例子:

我们可以惊奇的发现:

这里\(she\)的后缀\(he\)，和\(he\)是一样的，这时候我们想到了什么?

我们可以建立一个\(fail_{cur}\)的数组，在\(she\)后的\(e\)建立一个指向\(he\)中的\(e\)的指针。像这样

我们就可以很方便的进行匹配了。

现在我们的关键就在于如何求出\(fail\)。

假设我们有一点\(trie[cur][i]\)，它的父亲\(cur\)，若\(cur\)的\(fail\)已经求出，那么只会有两种情况

1. 我们的\(trie[cur][i]\)不为空，那么就直接把\(fail[trie[cur][i]]=fail[cur][i]\)，意思就是在自己的\(fail_{cur}\)下寻找一个\(i\)代表的数组。
2. 若\(trie[cur][i]\)为空，直接把这个点\(trie[cur][i]=trie[fail[cur]][i]\)

这样就好了。

我们查找的时候就一个字符一个字符的找，每一次针对一个字符，不停地根据\(fail\)往上跳，直到跳不动为止。

在这个过程中，我们要注意统计一次答案，就要把\(Trie\)中的计数器\(cnt\)清空为\(-1\)，代表跳到这里就跳不了了。

我们就可以轻松的打出代码

Code:

#include<iostream>
#include<queue>
using namespace std;
const int N = 1000005;
int trie[N][28], tot, num[N], fail[N];
queue<int> q;

void insert(string s) 
{
	int cur = 0;
	for(int i = 0; i < s.size(); i++) 
	{
		if(trie[cur][s[i]-'a'] == 0)
		{
			tot++; 
			trie[cur][s[i]-'a'] = tot;
		}
		cur = trie[cur][s[i]-'a'];
	}
	num[cur]++; //统计以cur结尾的单词出现的次数 
	return ;
}

void get_fail() //bfs构建fail数组 
{
	for(int i = 0; i < 26; i++) //根结点下面直接连的第一层结点，fail直接指向根结点0 
		if(trie[0][i]) 
			q.push(trie[0][i]);
			
	while(q.empty() == false) //队列中维护能够拓展fail值的结点 
	{
		int cur = q.front();
		q.pop();
		for(int i = 0; i < 26; i++) 
		{
			if(trie[cur][i])
			{
				//失配时，以trie[u][i]结尾的后缀尽量在trie中找一个与之相同的前缀（类似KMP） 
				fail[trie[cur][i]] = trie[fail[cur]][i];
				q.push(trie[cur][i]);
			}
			else //节点不存在，往上连，最多回到根结点0, 注意是trie不是fail数组 
				trie[cur][i] = trie[fail[cur]][i];
		}
	}
	return ;
}

int query(string t) //询问，t是文本串 
{
	int cur = 0, res = 0; //cur表示trie中的结点 
	for(int i = 0; i < t.size(); i++) 
	{
		cur = trie[cur][t[i] - 'a']; //获取t[i]所对应的结点 
		for(int j = cur; j && num[j] != -1; j = fail[j]) 
		{
	  		res += num[j];
			num[j] = -1; //标记为统计过 
		}
	}
	return res;
}

int main() 
{
	int n;
	string s;
	cin >> n;
	for(int i = 1; i <= n; i++) 
	{
		cin >> s;
		insert(s);
	}
	cin >> s; //文本串 
	get_fail();
	cout << query(s);
	return 0;
}