《AC自动机和TRIE图》由会员分享，可在线阅读，更多相关《AC自动机和TRIE图（20页珍藏版）》请在金锄头文库上搜索。
1、AC自动机和trie图,理顺思路,图中可以看到这样一些关系：extend-kmp 是kmp的扩展；ac自动机是kmp的多串形式；它是一个有限自动机；而trie图实际上是一个确定性有限自动机；ac自动机，trie图，后缀树实际上都是一种trie；后缀数组和后缀树都是与字符串的后缀集合有关的数据结构；trie图中的后缀指针和后缀树中的后缀链接 这两个概念及其一致。,回顾,KMP首先这个匹配算法，主要思想就是要充分利用上一次的匹配结果，找到匹配失败时，模式串可以向前移动的最大距离。这个最大距离，必须要保证不会错过可能的匹配位置，因此这个最大距离实际上就是模式串当前匹配位置的next数组值。也就是ma
2、xAj 是 Pi 的后缀 j si); if (h=head) h-si-fail=head;else h-si-fail=UpdateFail(h-fail,i); return; ,node *UpdateFail(node *p,int k) if (p-sk!=NULL) return p-sk;elseif (p=head) return p;else return UpdateFail(p-fail,k); ,以图为例,trie图,trie图实际上一个确定性自动机，比ac增加了确定性这个属性，对于ac自动机来说，当碰到一个不匹配的节点后可能要进行好几次回溯才能进行下一次匹配。但是对
3、于trie图来说，可以每一步进行一次匹配，每碰到一个输入字符都有一个确定的状态节点。从上面的图中我们也可以看到trie图的后缀节点跟ac自动机的后缀指针基本一致，区别在于trie图的根添加了了所有字符集的边。另外trie图还会为每个节点补上所有字符集中的字符的边，而这个补边的过程实际上也是一个求节点的后缀节点的过程，不过这些节点都是虚的，我们不把它们加到图中，而是找到它们的等价节点即它们的后缀节点，从而让这些边指向后缀节点就可以了。(比如上图中的黑节点c，它实际上并未出现在我们的初始tire里，但我们可以把它作为一个虚节点处理，把指向它的边指向它的后缀节点),两个概念,trie图主要利用两个概
4、念实现这种目的。一个是后缀节点，也就是每个节点的路径字符串去掉第一个字符后的字符串对应的节点。计算这个节点的方法，是通过它父亲节点的后缀节点，很明显它父亲的后缀节点与它的后缀节点的区别就是还少一个尾字符，设为c。所以节点的父节点的指针的c孩子就是该节点的后缀节点。但是因为有时候它父亲不一定有c孩子，所以还得找一个与父亲的c孩子等价的节点。于是就碰到一个寻找等价节点的问题。而trie图还有一个补边的操作，不存在的那个字符对应的边指向的节点实际上可以看成一个虚节点，我们要找一个现有的并且与它等价的节点，将这个边指向它。这样也实际上是要寻找等价节点。,等价节点与补编,我们看怎么找到一个节点的等价节点
5、，我们所谓的等价是指它们的危险性一致。那我们再看一个节点是危险节点的充要条件是：它的路径字符串本身就是一个危险单词，或者它的路径字符串的后缀对应的节点是一个危险节点。因此我们可以看到，如果这个节点对应的路径字符串本身不是一个危险单词，那它就与它的后缀节点是等价的。所以我们补边的时候，实际指向的是节点的后缀节点就可以了。,思维引导,trie图实际上对trie树进行了改进，添加了额外的信息。使得可以利用它方便的解决多模式串的匹配问题。跟kmp的思想一样，trie图也是希望利用现在已经匹配的信息，对未来的匹配提出指导。提出了一些新的概念。定义trie树上，从根到某个节点的路径上所有边上的字符连起来形
6、成的字符串称为这个节点的路径字符串。如果某个节点的路径字符串以一个危险字符串结尾，那么这个节点就是危险节点：也就是说如果到达这个点代表是匹配的状态；否则就是安全节点。 那么如何判断某个节点是否危险呢？,危险节点？,根节点显然是安全节点。一个节点是危险节点的充要条件是：它的路径字符串本身就是一个危险单词，或者它的路径字符串的后缀(这里特指一个字符串去掉第一个字符后剩余的部分)对应的节点(一个字符串对应的节点，是指从trie图中的根节点开始，依次沿某个字符指定的边到达的节点)是一个危险节点。那么如何求每一个节点的后缀节点呢？这里就可以里利用以前的计算信息，得到了。具体来说就是利用父亲节点的后缀节点
7、，我们只要记住当前节点的最后一个字符设为C，那么父亲节点的后缀节点的C分支节点就是要求的后缀节点了。首先我们限定，根节点的后缀节点是根本身，第一层节点的后缀节点是根节点。这样我们可以逐层求出所有节点的后缀节点。但是这个过程中，可能出现一个问题：父亲节点的后缀节点可能没有c分支。这时候该怎么办呢？,如上图所示如果设当前节点的父亲节点的后缀节点为w，我们假设w具有c孩子为，我们可以看到对于w的整个c子树来说，因为根本不存在通向它们的边c，它们也就不可能是不良字符串，这样这些节点的危险性也就等价与它们的后缀节点的危险性了，而它们的后缀节点，实际上就是w的后缀节点的c孩子，如此回溯下去，最后就能找到。
8、,trie图与AC自动机,其实Trie图所起到的作用就是建立一个确定性有限自动机DFA，图中的每点都是一个状态，状态之间的转换用有向边来表示。Trie图是在Tire的基础上补边过来的，其实他应该算是AC自动机的衍生，AC自动机只保存其后缀节点，在使用时再利用后缀节点进行跳转，并一直迭代到找到相应的状态转移为止，这个应该算是KMP的思想。这篇文章可以参考。而Trie图直接将AC自动机在状态转移计算后的值保存在当前节点，使得不必再对后缀节点进行迭代。所以Trie图的每个节点都会有|个状态转移（指字符集）。,构造方法,（1）构建Trie，并保证根节点一定有|个儿子。 （2）层次遍历Trie，计算后缀
9、节点，节点标记，没有|个儿子的对其进行补边。后缀节点的计算： （1）根结点的后缀节点是它本身。 （2）处于Trie树第二层的节点的后缀结点也是根结点。 （3）其余节点的后缀节点，是其父节点的后缀节点中有相应状态转移的节点（这里类似AC自动机的迭代过程）。节点标记： （1）本身就有标记。 （2）其后缀节点有标记。,补边： 用其后缀节点相应的状态转移来填补当前节点的空白。 最后Trie图中任意一个节点均有相应的状态转移，我们就用这个状态转移做动态规划。 设dpij表示第i个状态产生j个字符时，与DNA序列最小的改变值。 假设Tire图中根节点是0，则初始化dp00=1。 其后，对图进行BFS遍历，可知处于第j层时，就说明以产生了j长度的字符串。 dp00 = 1;for i = 1 to m do for 图中每条边(s1,ch,s2) do dps2i = mindps1i-1 + (txti-1 != ch); for 图中每个结点x do ans = mindpxm;,
