AC自动机相关Fail树和Trie图相关基础知识

TRIE图

定(xian)义(che)

Trie图实际上一个确定性有限状态自动机,比AC自动机增加了确定性这个属性.
对于AC自动机来说,当碰到一个不匹配的节点后可能要进行好几次回溯才能进行下一次匹配;但是对于trie图来说,可以每一步进行一次匹配,每碰到一个输入字符都有一个确定的状态节点。
trie图的后缀节点跟ac自动机的后缀指针基本一致，区别在于trie图的根添加了了所有字符集的边;另外trie图还会为每个节点补上所有字符集中的字符的边,而这个补边的过程实际上也是一个求节点的后缀节点的过程.不过这些节点都是虚的,我们不把它们加到图中,而是找到它们的等价节点即它们的后缀节点, 从而让这些边指向后缀节点就可以了.

实现

Trie图主要利用两个概念实现这种目的。 后缀节点 和 补边 操作.

相关操作

1. 后缀节点,也就是每个节点的路径字符串去掉第一个字符后的字符串对应的 节点.计算这个节点的方法,是通过它父亲节点的后缀节点,很明显它父亲的 后缀节点与它的后缀节点的区别就是还少一个尾字符,设为c,所以节点的父 节点的指针的c孩子就是该节点的后缀节点.但是因为有时候它父亲不一定有c孩子,所以还得找一个与父亲的c孩子等价的节点.于是就碰到一个寻找等价 节点的问题。
2. 而Trie图还有一个补边的操作,不存在的那个字符对应的边指向的节点实际 上可以看成一个虚节点,我们要找一个现有的并且与它等价的节点,将这个边 指向它.这样也实际上是要寻找等价节点。

实现相关

我们看怎么找到一个节点的等价节点,我们所谓的等价是指它们的危险性一致。那我们再看一个节点是危险节点的充要条件是:它的路径字符串本身就是一个危险单词,或者它的路径字符串的后缀对应的节点是一个危险节点.因此我们可以看到,如果这个节点对应的路径字符串本身不是一个危险单词.那它就与它的后缀节点是等价的.所以我们补边的时候,实际指向的是节点的后缀节点就可以了.

trie图实际上对trie树进行了改进，添加了额外的信息。
使得可以利用它方便的解决多模式串的匹配问题.跟kmp的思想一样,trie图也是希望利用现在已经匹配的信息,对未来的匹配提出指导.提出了一些新的概念。定义trie树上,从根到某个节点的路径上所有边上的字符连起来形成的字符串称为这个节点的路径字符串.如果某个节点的路径字符串以一个危险字符串结尾，那么这个节点就是危险节点：也就是说如果到达这个点代表是匹配的状态；否则就是安全节点。 那么如何判断某个节点是否危险呢？

根节点显然是安全节点。一个节点是危险节点的充要条件是：它的路径字符串本身就是一个危险单词，或者它的路径字符串的后缀(这里特指一个字符串去掉第一个字符后剩余的部分)对应的节点(一个字符串对应的节点，是指从trie图中的根节点开始，依次沿某个字符指定的边到达的节点)是一个危险节点。

那么如何求每一个节点的后缀节点呢？这里就可以里利用以前的计算信息，得到了。具体来说就是利用父亲节点的后缀节点，我们只要记住当前节点的最后一个字符设为C，那么父亲节点的后缀节点的C分支节点就是要求的后缀节点了。首先我们限定，根节点的后缀节点是根本身，第一层节点的后缀节点是根节点。这样我们可以逐层求出所有节点的后缀节点。但是这个过程中，可能出现一个问题：父亲节点的后缀节点可能没有c分支。这时候该怎么办呢？

如下图所示如果设当前节点的父亲节点的后缀节点为w，我们假设w具有c孩子为，我们可以看到对于w的整个c子树来说，因为根本不存在通向它们的边c，它们也就不可能是不良字符串，这样这些节点的危险性也就等价与它们的后缀节点的危险性了，而它们的后缀节点，实际上就是w的后缀节点的c孩子，如此回溯下去，最后就能找到。

总结

Trie图所起到的作用就是建立一个确定性有限自动机DFA，图中的每点都是一个状态，状态之间的转换用有向边来表示。Trie图是在Tire的基础上补边过来的，其实他应该算是AC自动机的衍生，AC自动机只保存其后缀节点，在使用时再利用后缀节点进行跳转，并一直迭代到找到相应的状态转移为止，这个应该算是KMP的思想。

过程：

1. 构建Trie，并保证根节点一定有|∑|个儿子。
2. 层次遍历Trie，计算后缀节点，节点标记，没有|∑|个儿子的对其进行补边。

后缀节点的计算：

1. 根结点的后缀节点是它本身。
2. 处于Trie树第二层的节点的后缀结点也是根结点。
3. 其余节点的后缀节点，是其父节点的后缀节点中有相应状态转移的节点（这里类似AC自动机的迭代过程）。

节点标记：

1.本身就有标记。
2.其后缀节点有标记。

补边：

用其后缀节点相应的状态转移来填补当前节点的空白。
最后Trie图中任意一个节点均有相应的状态转移，我们就用这个状态转移做动态规划。