什么是AC自动机？

百度百科

Aho-Corasick automaton，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。

要学会AC自动机，我们必须知道什么是Trie，也就是字典树。Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

AC自动机有什么作用？

快速寻找多个字串与原串的关系，是多个字符串的kmp匹配算法

怎么实现AC自动机？

①trie字典树部分

这里只需要进行一个insert函数书写即可，把每个字串插入到trie树中，不同于字典树模板，这个insert函数需要记录词尾。

具体代码

void insert(string a)

{

  int rt=0;

  for(int i=0;i<a.size();i++)

  {

    int id=a[i]-'a';

    if(!trie[rt][id])

    trie[rt][id]=++cnt;

    rt=trie[rt][id];

  }

  bk[rt]++;

}

②KMP部分

build函数

①枚举根节点的各个孩子如果存在就把他们入队

queue<int> q;

  memset(fail,0,sizeof(fail));

  for(int i=0;i<26;i++)

  if(trie[0][i])

  q.push(trie[0][i]);

②BFS进行搜索

转载于洛谷日报第44期

下面介绍构建fail指针的基础思想：（强调！基础思想！基础！）

构建fail指针，可以参考KMP中构造next数组的思想。

我们利用部分已经求出fail指针的结点推导出当前结点的fail指针。具体我们用BFS实现：

考虑字典树中当前的节点u，u的父节点是p，p通过字符c的边指向u。

假设深度小于u的所有节点的fail指针都已求得。那么p的fail指针显然也已求得。

我们跳转到p的fail指针指向的结点fail[p]；

如果结点fail[p]通过字母cc连接到的子结点w存在：

则让u的fail指针指向这个结点w（fail[u]=w）。

相当于在pp和fail[p]后面加一个字符cc，就构成了fail[u]。

如果fail[p]通过字母cc连接到的子结点w不存在：

那么我们继续找到fail[fail[p]]指针指向的结点，重复上述判断过程，一直跳fail指针直到根节点。

如果真的没有，就令fail[u]=根节点。

如此即完成了fail指针的构建。

while(!q.empty())

  {

    int k=q.front();

    q.pop();

    for(int i=0;i<26;i++)

    {

      if(trie[k][i])

      {

        fail[trie[k][i]]=trie[fail[k]][i];

        q.push(trie[k][i]);

      }

      else

      trie[k][i]=trie[fail[k]][i];

    }

  }

完整代码

void build()

{

  queue<int> q;

  memset(fail,0,sizeof(fail));

  for(int i=0;i<26;i++)

  if(trie[0][i])

  q.push(trie[0][i]);

  while(!q.empty())

  {

    int k=q.front();

    q.pop();

    for(int i=0;i<26;i++)

    {

      if(trie[k][i])

      {

        fail[trie[k][i]]=trie[fail[k]][i];

        q.push(trie[k][i]);

      }

      else

      trie[k][i]=trie[fail[k]][i];

    }

  }

}

个人的理解是，这一部分首先把根的子节点入队，然后bfs建立字典图，感觉跟并查集有点类似

③查询部分

这里没有什么好说的，先和并查集的感觉，找到最后的叶子节点然后就是一顿查询fail，这里的查询是查询字串总共有多少个出现在了原串中，所以要bk[j]=-1，然后判断条件还得加上bk[j]!=-1

int search(string a)

{

  int rt=0,ans=0;

  for(int i=0;i<a.size();i++)

  {

    rt=trie[rt][a[i]-'a'];

    for(int j=rt;j&&bk[j]!=-1;j=fail[j])

    ans+=bk[j],bk[j]=-1;

  }

  return ans;

}

完整代码(洛谷 P3808 【模板】AC自动机（简单版）)

#include <bits/stdc++.h>

using namespace std;

int trie[10000000][30];

int bk[10000000];

int fail[10000000];

int cnt;

void insert(string a)

{

  int rt=0;

  for(int i=0;i<a.size();i++)

  {

    int id=a[i]-'a';

    if(!trie[rt][id])

    trie[rt][id]=++cnt;

    rt=trie[rt][id];

  }

  bk[rt]++;

}

void build()

{

  queue<int> q;

  memset(fail,0,sizeof(fail));

  for(int i=0;i<26;i++)

  if(trie[0][i])

  q.push(trie[0][i]);

  while(!q.empty())

  {

    int k=q.front();

    q.pop();

    for(int i=0;i<26;i++)

    {

      if(trie[k][i])

      {

        fail[trie[k][i]]=trie[fail[k]][i];

        q.push(trie[k][i]);

      }

      else

      trie[k][i]=trie[fail[k]][i];

    }

  }

}

int search(string a)

{

  int rt=0,ans=0;

  for(int i=0;i<a.size();i++)

  {

    rt=trie[rt][a[i]-'a'];

    for(int j=rt;j&&bk[j]!=-1;j=fail[j])

    ans+=bk[j],bk[j]=-1;

  }

  return ans;

}

int main()

{

  ios::sync_with_stdio(0);

  cin.tie(0);

  cout.tie(0);

  int n;

  cin>>n;

  while(n--)

  {

    string a;

    cin>>a;

    insert(a);

  }

  build();

  string a;

  cin>>a;

  cout<<search(a);

}

巴特西

浅谈AC自动机模板