AC自动机

https://oi-wiki.org/string/ac-automaton/
AC 自动机是 以 TRIE 的结构为基础 ，结合 KMP 的思想 建立的。

简单来说，建立一个 AC 自动机有两个步骤：

基础的 TRIE 结构：将所有的模式串构成一棵 。
KMP 的思想：对 TRIE 树上所有的结点构造失配指针。
然后就可以利用它进行多模式匹配了。
字典树构建¶
AC 自动机在初始时会将若干个模式串丢到一个 TRIE 里，然后在 TRIE 上建立 AC 自动机。这个 TRIE 就是普通的 TRIE，该怎么建怎么建。

这里需要仔细解释一下 TRIE 的结点的含义，尽管这很小儿科，但在之后的理解中极其重要。TRIE 中的结点表示的是某个模式串的前缀。我们在后文也将其称作状态。一个结点表示一个状态，TRIE 的边就是状态的转移。

失配指针¶
AC 自动机利用一个 fail 指针来辅助多模式串的匹配。

状态 的 fail 指针指向另一个状态 ，其中 ，且 是 的最长后缀（即在若干个后缀状态中取最长的一个作为 fail 指针）。对于学过 KMP 的朋友，我在这里简单对比一下这里的 fail 指针与 KMP 中的 next 指针：

共同点：两者同样是在失配的时候用于跳转的指针。
不同点：next 指针求的是最长 Border（即最长的相同前后缀），而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。
因为 KMP 只对一个模式串做匹配，而 AC 自动机要对多个模式串做匹配。有可能 fail 指针指向的结点对应着另一个模式串，两者前缀不同。

没看懂上面的对比不要急（也许我的脑回路和泥萌不一样是吧），你只需要知道，AC 自动机的失配指针指向当前状态的最长后缀状态即可。

AC 自动机在做匹配时，同一位上可匹配多个模式串。

构建指针

例如：求出目标字符串集合{“nihao”,”hao”,”hs”,”hsr”}在给定文本”sdmfhsgnshejfgnihaofhsrnihao”中所有可能出现的位置。解决这个问题，我们一般的办法就是在文本串中对每个目标字符串单独查找，并记录下每次出现的位置。显然这样的方式能够解决问题，但是在文本串较大、目标字符串众多的时候效率比较低。为了提高效率，贝尔实验室于1975年发明著名的多模字符串匹配算法——AC自动机。AC自动机在实现上要依托于Trie树（也称字典树）并借鉴了KMP模式匹配算法的核心思想。实际上你可以把KMP算法看成每个节点都仅有一个孩子节点的AC自动机。

1. AC自动机及其运行原理
   2.1 初识AC自动机

AC自动机的基础是Trie树。和Trie树不同的是，树中的每个结点除了有指向孩子的指针（或者说引用），还有一个fail指针，它表示输入的字符与当前结点的所有孩子结点都不匹配时(注意，不是和该结点本身不匹配)，自动机的状态应转移到的状态（或者说应该转移到的结点）。fail指针的功能可以类比于KMP算法中next数组的功能。

我们现在来看一个用目标字符串集合{abd,abdk, abchijn, chnit, ijabdf, ijaij}构造出来的AC自动机

其中根结点不存储任何字符，根结点的fail指针为null。虚线表示该结点的fail指针的指向，所有表示字符串的最后一个字符的结点外部都用红圈表示，我们称该结点为这个字符串的终结结点。每个结点实际上都有fail指针，但为了表示方便，本文约定一个原则，即所有指向根结点的 fail虚线都未画出。

从上图中的AC自动机，我们可以看出一个重要的性质：每个结点的fail指针表示由根结点到该结点所组成的字符序列的所有后缀　和　整个目标字符串集合（也就是整个Trie树）中的所有前缀 两者中最长公共的部分。

比如图中，由根结点到目标字符串“ijabdf”中的 ‘d’组成的字符序列“ijabd”的所有后缀在整个目标字符串集{abd,abdk, abchijn, chnit, ijabdf, ijaij}的所有前缀中最长公共的部分就是abd，而图中d结点（字符串“ijabdf”中的这个d）的fail正是指向了字符序列abd的最后一个字符。

2.2 AC自动机的运行过程：

1）表示当前结点的指针指向AC自动机的根结点，即curr = root

2）从文本串中读取（下）一个字符

3）从当前结点的所有孩子结点中寻找与该字符匹配的结点，

若成功：判断当前结点以及当前结点fail指向的结点是否表示一个字符串的结束，若是，则将文本串中索引起点记录在对应字符串保存结果集合中（索引起点= 当前索引-字符串长度+1）。curr指向该孩子结点，继续执行第2步

若失败：执行第4步。

4）若fail == null（说明目标字符串中没有任何字符串是输入字符串的前缀，相当于重启状态机）curr = root, 执行步骤2，

否则，将当前结点的指针指向fail结点，执行步骤3)

现在，我们来一个具体的例子加深理解，初始时当前结点为root结点，我们现在假设文本串text = “abchnijabdfk”。

1. 构造AC自动机的方法与原理
   3.1 构造的基本方法

首先我们将所有的目标字符串插入到Trie树中，然后通过广度优先遍历为每个结点的所有孩子节点的fail指针找到正确的指向。

确定fail指针指向的问题和KMP算法中构造next数组的方式如出一辙。具体方法如下

1）将根结点的所有孩子结点的fail指向根结点，然后将根结点的所有孩子结点依次入列。

2）若队列不为空：

2.1）出列，我们将出列的结点记为curr, failTo表示curr的fail指向的结点，即failTo = curr.fail

2.2) a.判断curr.child[i] == failTo.child[i]是否成立，

       成立：curr.child[i].fail = failTo.child[i]，



       不成立：判断 failTo == null是否成立



              成立： curr.child[i].fail == root



              不成立：执行failTo = failTo.fail，继续执行2.2）



   b.curr.child[i]入列，再次执行再次执行步骤2)

若队列为空:结束

3.2 通过一个例子来理解构造AC自动机的原理

每个结点fail指向的解决顺序是按照广度优先遍历的顺序完成的，或者说层序遍历的顺序进行的，也就是说我们是在解决当前结点的孩子结点fail的指向时，当前结点的fail指针一定已指向了正确的位置。

为了说明问题，我们再次强调“每个结点的fail指针表示：由根结点到该结点所组成的字符序列的所有后缀 和 整个目标字符串集合（也就是整个Trie树）中的所有前缀 两者中最长公共的部分”。

以上图所示为例，我们要解决结点x1的某个孩子结点y的fail的指向问题。已知x1.fail指向x2，依据x1结点的fail指针的含义，我们可知红色实线椭圆框内的字符序列必然相等，且表示了最长公共部分。依据y.fail的含义，如果x2的某个孩子结点和结点y表示的字符相等，那么y.fail就该指向它。

如果x2的孩子结点中不存在结点y表示的字符，这个时候该怎么办？由于x2.fail指向x3，根据x2.fail的含义，我们可知绿色方框内的字符序列必然相等。显然，如果x3的某个孩子结点和结点y表示的字符相等，那么y.fail就该指向它。

如果x3的孩子结点中不存在结点y表示的字符，我们可以依次重复这个步骤，直到xi结点的fail指向null，这时说明我们已经到了最顶层的根结点，这时，我们只需要让ｙ.fail = root即可。

构造的过程的核心本质就是，已知当前结点的最长公共前缀的前提下，去确定孩子结点的最长公共前缀。这完全可以类比于KMP算法的next数组的求解过程。

3.2.1 确定图中h结点fail指向的过程

现在我们假设我们要确定图中结点c的孩子结点h的fail指向。图中每个结点都应该有表示fail的虚线，但为了表示方便，按照本文约定的原则，所有指向根结点的 fail虚线均未画出。

经常会遇到一类需求，在一段字符串中查找所有能匹配上的模式，比如查找一段文字匹配上字典中哪些短语。这时为了高效处理，就会考虑 AC 自动机，即 Aho-Corasick 自动机算法。它的核心思想是通过有限自动机巧妙地将字符比较转化为了状态转移。
通过 AC 自动机能做到匹配时不需要回溯，而且时间复杂度为 O(n)，即时间复杂度与词典的规模无关。

AC自动机
AC自动机主要是将 n 个模式串构建成一个确定性的树形有限状态机，然后将主串作为该有限状态机的输入，使该状态机进行状态的转换，当到达某些特定的状态时则说明发生模式匹配。

在状态机内部，可以看到有实线和虚线箭头，优先以实线标明方向转换状态，当无法实线转换时才使用虚线转换。
另外，当转换到图中红圈位置时说明发生了模式匹配，比如对于he，从根节点到1再到2，此时符合he，说明发生了模式匹配。
根据上图你可以试试看ushers会匹配出哪些模式，并且比划下状态的转换过程。
AC的三个函数
AC自动机包含了三个核心函数，基本上理解了他们就搞懂AC了。

goto函数，用来指导状态转换，即在当前状态下，输入一个字符后该转到哪个状态

failure函数，用来指导匹配失败时的状态转换，即在当前状态下，输入一个字符后没办法根据实线进行转换了，此时根据虚线进行转换

output函数，描述哪些状态下发生了匹配，匹配的模式是什么
实现
实现AC自动机时一般都会用TRIE树结构，那么就会定义一个ACTrieNode类，包含了子节点、值、output、failure节点等等属性。
public class ACTrieNode {
private ACTrieNode[] children;
private byte[] value;
private boolean deleted = false;
private int status;
private ACArray[] results = null;
private ACTrieNode failureNode;
private static String encoding = “utf-8”;
}

Aho-Corasick自动机是一种多字符串匹配的算法，通过将模式串预处理为确定有限状态自动机，匹配复杂度为O(n)，即与模式串的数量和长度无关。疑问：能同时获得匹配字符串的位置吗？如何多次匹配同一字符串？各自的位置呢？

AC算法中有三个核心表，分别是：

success表： 这一步匹配成功了，下一步可以匹配哪些

failure表： 这一步匹配失败了，怎么转移到新的路径匹配

emits表： 匹配到某个节点，可以输出哪些内容

三个核心问题：

1、如何构建这些表？2、如何存储这些表？3、如何查询这些表？

下面分别一一作答。

success表的构建：success非常容易构建，按照需要匹配的字符串构建成一棵树就可以了，如下图中的实线部分，其中0号是root节点，不存储具体字符。这张表里包含了he, hers, his, she这几个单词。

failure表的构建：上图中的失败指针即为虚线，指如果到这一节点匹配成功了，但是在其子节点匹配失败了，该走向哪一个节点。构建方法是这样的：对于一个节点C，标识字符a，顺着C的父亲节点的失配指针走，走到第一个有儿子也是a的节点T，那么C的失败指针就指向T的标识a的儿子节点。如果找不到这个节点，那么失败指针指向Root。在实际操作时，这个建构过程要求父亲节点的失败指针已经建好，而且一层层都要建好，所以采用bfs实现failure表的构建。比如，在上图中，节点5的父节点为4，4的失败指针指向1，1的子节点中包含字符e的为2，所以5的失败指针指向2。

emits表的构建：猜测把失败指针指向的节点的内容copy过来，比如上图中，节点5的失败指针指向2，2是一个emit节点，包含的内容是he，把he拷贝到节点5的emit表中即可。用链表会更好吧

success表的存储：大部分实现都是采用了字典，不过性能可能会受影响

我们经常用的字符串方法indexOf，都是判定两个字符串的包含关系，底层使用类似KMP，BM， Sunday这样的算法。如果我们要判断一个长字符串是否包含多个短字符串呢？比如在一篇文章找几个敏感词，在DNA串中找几个指定的基因对pattern进行预处理，如果我们的模式串存在多个，则不适合了，我们就需要用到一种多模式匹配算法。

最著名的多模式匹配算法为AC自动机，它是由贝尔实验室的两位研究人员 Alfred V. Aho 和 Margaret J.Corasick 于1975年发明的，几乎与KMP算法同时问世，至今日仍然在模式匹配领域被广泛应用。

AC自动机的核心算法仍然是寻找模式串内部规律，达到在每次失配时的高效跳转。这一点与单模式匹配KMP算法是一致的。不同的是，AC算法寻找的是模式串之间的相同前缀关系。

在KMP算法中，对于模式串”abcabcacab”，我们知道非前缀子串abc(abca)cab是模式串的一个前缀(abca)bcacab，而非前缀子串ab(cabca)cab不是模式串abcabcacab的前缀，根据此点，我们构造了next数组，实现在匹配失败时的跳转。

而在多模式环境中，AC自动是使用前缀树来存放所有模式串的前缀，然后通过失配指针来处理失配的情况。它大概分为三个步骤：构建前缀树（生成goto表），添加失配指针（生成fail表），模式匹配（构造output表）。下面，我们拿模式集合[say, she, shr, he, her]为例，构建一个AC 自动机。

构建前缀树
将模式串逐字符放进Trie树。

class Trie {
constructor() {
this.root = new Node(“root”);
}
insert(word) {
var cur = this.root;
for (var i = 0; i < word.length; i++) {
var c = word[i];
var node = cur.children[c];
if (!node) {
node = cur.children[c] = new Node(word[i]);
}
cur = node;
}
cur.pattern = word; //防止最后收集整个字符串用
cur.endCount++; //这个字符串重复添加的次数
}
}
function createGoto(trie, patterns) {
for (var i = 0; i < patterns.length; i++) {
trie.insert(patterns[i]);
}
}
然后我们尝试用它处理字符串sher。理想情况下是这样：

很遗憾，前缀树只会顺着某一路径往下查找，最多到叶子节点折回树节点，继续选择另一条路径。因此我们需要添加一些横向的路径，在失配时，跳到另一个分支上继续查找，保证搜索过的节点不会冗余搜索。

添加失配指针
AC自动机的前缀树的节点都应该存在fail指针。下图中，红色的箭头就是失配指针。它表示文本串在当前节点失配后，我们应该到哪个节点去继续匹配。

很显然，对于每个节点，其失配指针应该指向其他子树中的表示同一字符的那些节点，并且它与其子树能构成剩下的最长后缀。即，我们要匹配sher, 我们已经在某一子树中命中了sh，那么我们希望能在另一个子树中命中er。

到这里，你是不是发现fail指针和KMP中的next指针简直一毛一样？它们都被称为“失配指针”。将Trie树上的每一个点都加上fail指针，它就变成了AC自动机。AC自动机其实就是Trie + KMP。

因此根据补上一些失配指针，我们的AC自动机应该长成这样的。

现在的问题是，如何求fail指针？联系KMP算法的next数组的意义，容易发现root的每个儿子的fail都指向root（前缀和后缀是不会包含整个串的）。也就是上图中root所连的s和h的fail都指向root。若已经求得sh所在点的fail，我们来考虑如何求she所在点的fail。根据sh所在点的fail得到h是sh的最长后缀，而h又有儿子e，因此she的最长后缀应该是he，其fail指针就指向he所在点。

概括AC自动机求fail指针的过程：

1.对整个字典树进行宽度优先遍历。
2.若当前搜索到点x，那么对于x的第i个儿子(也就是代表字符i的儿子)，一直往x的fail跳，直到跳到某个点也有i这个儿子，x的第i个儿子的fail就指向这个点的儿子i。

function createFail(ac) {
var root = ac.root;
var queue = [root]; //root所在层为第0层
while (queue.length) {
//广度优先遍历
var node = queue.shift();
if (node) {
//将其孩子逐个加入列队
for (var i in node.children) {
var child = node.children[i];
if (node === root) {
child.fail = root; //第1层的节点的fail总是指向root
} else {
var p = node.fail; //第2层以下的节点, 其fail是在另一个分支上
while (p) {
//遍历它的孩子，看它们有没与当前孩子相同字符的节点
if (p.children[i]) {
child.fail = p.children[i];
break;
}
p = p.fail;
}
if (!p) {
child.fail = root;
}
}
queue.push(child);
}
}
}
}
模式匹配
我们从根节点开始查找，如果它的孩子能命中目标串的第1个字符串，那么我们就从这个孩子的孩子中再尝试命中目标串的第2个字符串。否则，我们就顺着它的失配指针，跳到另一个分支，找其他节点。

如果都没有命中，就从根节点重头再来。

当我们节点存在表示有字符串在它这里结束的标识时（如endCound, isEnd），我们就可以确认这字符串已经命中某一个模式串，将它放到结果集中。如果这时长字符串还没有到尽头，我们继续收集其他模式串。

代码如下：

function match(ac, text) {
var root = ac.root, p = root, ret = [], unique = {};
for (var i = 0; i < text.length; i++) {
var c = text[i];
while (!p.children[c] && p != root) {
p = p.fail; // 失配指针发挥作用 by 司徒正美
}
p = p.children[c];
if (!p) {
p = root; // 如果没有匹配的，从 root 开始重新匹配
}
var node = p;
while (node != root) {
// 收集出可以匹配的模式串
if (node.endCount) {
var pos = i - node.pattern.length + 1;
console.log(匹配模式串 ${node.pattern}其起始位置在${pos})
if (!unique[node.pattern]) { //by 司徒正美
unique[node.pattern] = 1;
ret.push(node.pattern);
}
}
node = node.fail;
}
}
return ret;
}

var ac = new Trie();
createGoto(ac, [“she”, “shr”, “say”, “he”, “her”]);
createFail(ac);
console.log(match(ac, “one day she say her has eaten many shrimps”));

形式上，AC 自动机基于由若干模式串构成的 Trie 树，并在此之上增加了一些 fail 边；本质上，AC 自动机是一个关于若干模式串的 DFA（确定有限状态自动机），接受且仅接受以某一个模式串作为后缀的字符串。

并且，与一般自动机不同的，AC 自动机还有 关于某个模式串的接受状态（我自己起的名字..），也就是与某个模式串匹配（以某个模式串为后缀）的那些状态。

AC 自动机怎样构建？
大致分为两个过程：

构建模式串组成的 Trie 树。
连 fail 边。
第一个过程不用讲吧。

fail 边是什么？
fail 边是 AC 自动机上一种特殊的边，其意义为：当 u 在 Trie 树上没有字符 c 的出边时，将 δ(u,c) 定义为 δ(fail(u),c)（特例：初始状态若不存在某字符出边则连向自己，也可以理解为 ∀c∈Σ,δ(fail(start),c)=start）。

另外，fail 边的作用类似于 KMP 算法中的 next 数组。

fail 边怎么连？
我们发现一个状态的 fail 边连向的其实就是这个状态的一个自动机上最长真后缀。

为什么呢..感性理解一下，失配了就不看前几位了..

然后就很好连了：对 Trie 树进行 BFS，将 fail(δ(u,c)) 设为 δ(fail(u),c)。因为一个串加上一个字符的最长真后缀就是这个串的最长真后缀加上这个字符..

另外，将 δ(u,c) 设为 δ(fail(u),c) 可以显式地在代码中完成。

再另外，要么 BFS 开始的时候将根节点的孩子入队，要么将 fail(root) 的每个儿子都设为 root。否则根的儿子的 fail 边会连向自己。（也就是上文所述的“特例”。）

for (i = 0; i < 26; ++i) tr[0][i] = 1;

q.push(1);

while (!q.empty())
{
u = q.front();
q.pop();
for (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];
}
}
fail 树
由于每个点都只连出一条 fail 边，且连到的点对应的字符串长度更小，所以 fail 边构成了一棵 fail 树。

如果学过 SAM 的话，可能会发现 fail 树和 parent 树很像..实际上它们具有的性质是相同的，然而构成它们的状态不同——parent 树是所有 right 集合等价类（也就是 SAM 上的所有节点），而 fail 树是 Trie 上的每个前缀（也就是 AC 自动机上的所有节点）。

作为一个自动机，我还没讲 AC 自动机的接受状态是哪些..其实就是 Trie 树上的那些终止节点在 fail 树上的整个子树的并。

而 关于某个模式串的接受状态，也就是与某个模式串匹配（以某个模式串为后缀）的那些状态，就是那个串在 Trie 树上的终止节点在 fail 树上的子树。知道这个也就知道怎么用 AC 自动机进行多模式串匹配了（建出 fail 树，记录自动机上的每个状态被匹配了几次，最后求出每个模式串在 Trie 上的终止节点在 fail 树上的子树总匹配次数就可以了）

与 KMP 之间的关系
放在最后面是因为我认为 KMP 并不是 AC 自动机的前置知识..然而他们之间的确有着千丝万缕的联系。

「KMP 是个自动机」

要是早有人告诉我这句话估计我早就（真正地）学会 KMP 了..

KMP 自动机的主体是一条链，加上了一些“next 边”（其实就是 AC 自动机的 fail 边）。

而 KMP 自动机之于 AC 自动机，就像 SAM 之于广义 SAM。

也就是很多人常说的一句话：AC 自动机就是 Trie 上 KMP。

递归地计算转移函数
简介
“将 δ(u,c) 设为 δ(fail(u),c)”这一步是可以不去显式完成的，并且，在绝大多数情况下（事实上我并不知道任何反例）这样做复杂度是线性的，可以将复杂度中的字符集大小去掉，并节省空间。

做法非常简单：当你需要 δ(u,c) 而其没有定义时，递归地去计算 δ(fail(u),c)。

构建 fail 的过程复杂度为线性
一个节点到根的路径上这些点总共跳 fail 的次数不会超过其深度。

所以总共跳 fail 次数不会超过 Trie 树所有叶子的深度和。

证完了。

将字符串输入进自动机复杂度为线性
每输入一个字符串最多深度加一。

每次跳 fail 深度减一。

https://blog.csdn.net/lemon_tree12138/article/details/49335051

Aho-Corasick automaton(后面心均以AC代替)，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。

  AC自动机算法分为3步：构造一棵Trie树，构造失效指针和模式匹配过程。而这3步就是AC自动机算法的精髓所在，分别对应我们后面马上要说的3个函数：success,failure和emits.

3.特别说明
3.0.学前导读
  在学习本文之前，需要两个方面的知识背景。一个是Trie树，一个是KMP算法。大家可以移步到两面的两个链接中，学习一下。之后，回过头来再看我们的AC自动机，就可以会比较容易消化，也能更容易理解其中的精髓。

  《数据结构：字典树的基本使用》

  《算法：模式匹配之KMP算法》

3.1.本文参考
  《Aho-Corasick算法的Java实现与分析-码农场》

4.一睹为快
  以经典的ushers为例，模式串是he/ she/ his /hers，文本为“ushers”。构建的自动机如图：

5.原理说明
5.0.算法比较
  正如前面所说，AC算法是基于Trie树且是KMP模式匹配算法的扩展。那么这里我们就可以从两个方面来作为切入点，详细说明一下AC算法或是AC自动机究竟是何物。

  首先明白两点：Trie树的核心点是状态转移，KMP模式匹配的核心点是减少重复匹配。

  先说Trie树吧。在之前的博客中，我还是用了很多的篇幅来说Trie树，不算这一篇的话，也有3篇文章或多或少都和Trie树扯上点边儿。前面的Trie树中，每个节点既是字符本身，又是节点的状态(DAT则不是这样)。节点为字符本身，这个好理解，那又是节点的状态这个要怎么解释呢？因为我们知道，当我们在遍历的过程中，走到某一个点的时候，比如说：目前有两个字典字符串：T1：”abcde”和T2：”abdef”，当我们在遍历的过程中走了”abcd”且停在了’d’字符上.这个时候，我们可以认定目前是处于字符串T1上的。因为当前节点可以代表其状态。而在T1和T2中，两个’d’节点的状态是不同的。而Trie树的状态转移则可以理解为，我们在遍历到节点d的时候，动态确定节点d的下一个状态，即节点e。

  再说说KMP模式匹配。在KMP模式匹配的过程中，我们使用到了一个next函数(如果你高兴，也可以说这是一张next表)。next函数的作用是，当我们在匹配的过程中，发生了匹配失败的时候，可以将模式串向前滑动n个字符，从而省去了n次的比较操作。而具体的操作方法及说明，我在之前的博客中也有介绍，这里不再详细说明。

  试想一下，如果我们要匹配一个文本文件d(举例文件的目的是为了说明，这个匹配字符串可能会是一个很长的字符串)，使用Trie树的匹配方式，依然需要对d进行循环遍历，就像朴素模式匹配那样。Trie树减少的只是在Trie树中重合的部分，所以时间复杂会相当高。那么，KMP算法呢？对于KMP算法，我们要清楚一点。KMP算法是给模式串生成next函数，在多模式的情况下，我们需要生成很多的next函数，再对每个模式进行匹配。这显然也并不理想。

  基于以上这两点，我们的AC算法诞生了。

5.1.原理
  AC为了克服Trie树中无效匹配和KMP算法需要一个一个去匹配，设计了一种新的算法。算法中需要维护三个函数，分别是：

  success:从一个状态成功转移到另一个状态(有时也叫goto表或是success表)。

  failure:从一个状态按照普通流程会匹配失败，这时我们要通过failure函数来做状态跳转。

  emits:命中一个模式串(也称为output表)。

  从上面的状态转移图中就可以看出来，整个节点+实线就是success函数；而虚线就是failure函数；红色节点则是emits函数。

6.代码实现过程及说明
6.0.整体实现过程流程图
  

6.1.创建Trie树
  其实AC自动机是建立在Trie的基础之上的，从上面的状态转移图中就可以获得这一信息。而在AC算法的3个函数中的success函数就是一种Trie树。

/**
* 构造一棵trie树
*
* @param trieConfig
*/
public Trie(TrieConfig trieConfig) {
this(trieConfig, true);
}

public Trie(TrieConfig trieConfig, boolean ascii) {

    this.trieConfig = trieConfig;

    if (ascii) {

        this.rootState = new AsciiState();

    } else {

        this.rootState = new UnicodeState();

    }

}  

6.2.success表的创建
  从上面我们知道，success函数的功能就是构建一个棵Trie树。关键是如何构建，因为这个Trie树的构建和我们之前说的那并不完全相同。

  在AC算法中，我们把Trie树中的节点就直接称为状态(State).在创建状态转移表的过程中，则是利用了递推的思想。我们在添加字典的过程中，其实是去计算当前字符对应的下一下状态。详细过程，请参见如下代码：

/**
* 转移到下一个状态
*
* @param character 希望按此字符转移
* @param ignoreRootState 是否忽略根节点，如果是根节点自己调用则应该是true，否则为false
* @return 转移结果
*/
private State nextState(Character character, boolean ignoreRootState) {
State nextState = this.success.get(character);
if (!ignoreRootState && nextState == null && this.rootState != null) {
nextState = this.rootState;
}
return nextState;
}

@Override

public State nextStateIgnoreRootState(Character character) {

    return nextState(character, true);

}

 

@Override

public State addState(Character character) {

    State nextState = nextStateIgnoreRootState(character);

    if (nextState == null) {

        nextState = new UnicodeState(this.depth + 1);

        this.success.put(character, nextState);

    }

    return nextState;

}  

6.3.failure表的创建
  failure表的创建是一个广度优先搜索的过程。在这个过程中，我们通过不断遍历状态Trie树。详细编码过程如下：

/**
* 建立failure表
*/
private void constructFailureStates() {
Queue queue = new LinkedBlockingDeque();

    // 第一步，将深度为1的节点的failure设为根节点

    for (State depthOneState : this.rootState.getStates()) {

        depthOneState.setFailure(this.rootState);

        queue.add(depthOneState);

    }

    this.failureStatesConstructed = true;

 

    // 第二步，为深度 > 1 的节点建立failure表，这是一个bfs

    while (!queue.isEmpty()) {

        State currentState = queue.remove();

 

        for (Character transition : currentState.getTransitions()) {

            State targetState = currentState.nextState(transition);

            queue.add(targetState);

 

            State traceFailureState = currentState.failure();

            while (traceFailureState.nextState(transition) == null) {

                traceFailureState = traceFailureState.failure();

            }

            State newFailureState = traceFailureState.nextState(transition);

            targetState.setFailure(newFailureState);

            targetState.addEmit(newFailureState.emit());

        }

    }

}  

6.4.emits命中(output表的创建)
  关于output表的创建，其实跟Trie树中的结束结点标志很类似。都是在模式串的末尾对状态进行修改的过程。而output表则是在状态节点对象中以组合的方式来体现。

/**
* 添加一个模式串
*
* @param keyword
*/
public void addKeyword(String keyword) {
…
currentState.addEmit(keyword);
}

/**

 * 添加一个匹配到的模式串（这个状态对应着这个模式串)

 *

 * @param keyword

 */

public void addEmit(String keyword) {

    if (this.emits == null) {

        this.emits = new TreeSet<String>();

    }

    this.emits.add(keyword);

}  

7.GitHub 源码
https://github.com/qwhai/jac-core