[POJ]POJ_2778_DNA_Sequence

It's well known that DNA Sequence is a sequence only contains A, C, T and G, and it's very useful to analyze a segment of DNA Sequence，For example, if a animal's DNA sequence contains segment ATC then it may mean that the animal may have a genetic disease. Until now scientists have found several those segments, the problem is how many kinds of DNA sequences of a species don't contain those segments. 

Suppose that DNA sequences of a species is a sequence that consist of A, C, T and G，and the length of sequences is a given integer n. 

题目的大意就是给定一组DNA的子序列，要我们计算长度为N的DNA序列中不包含这些子序列的数量有多少个。多串匹配的问题我们首先构造AC自动机，{ACG, C}如下图所示：

实线表示的是Trie的部分，虚线表示的是Fail指针(root的fail指针指向自己，这里我们未画出)。AC自动机表示了根据输入文本应该进行的状态转移，我们可以看到红色的状态是危险的状态，是我们无论如何都想避免到达的。如果我们把每个节点对应不同输入的状态转移画出来，可以得到对应的有向图：

对于一个节点，我们需要把对应的child指针指向接受输入之后应该指的方向。比如对于图中的1节点，输入a之后会走fail指针回到根节点0，但是fail指针的移动是不消耗输入字符的，所以我们可以继续move到a。所以对应的children[a]指针就应该指向a自身。同理对于0节点的children[t]和children[g]，我们把他们指向root而不是留为nullptr。因为现在我们是对每个节点对应的每个输入建图，而不是仅仅保有在AC自动机的所拥有的边。建这个图的过程并不复杂，在我们建fail指针的时候，，对于所有不同的输入:

• 如果其有对应的子节点children[c]，那么我么已经有有对应的边连接状态转移
• 如果其没有对应的子节点children[c]，我们直接把其连向对应fail指针的对应子节点fail->children[c]。这里我们把root的fail指针设为root，这样一层一层下来的话，其一定可以指向对应c输入之后需要转向的节点。

如上图所示，可以看出来我们想求的是从0开始以任意一个合法状态{1, 2}结尾的长度为N的路径的数目。我们在这篇文章介绍过，邻接矩阵M的k次方，M^k[i][j]表示的是从i节点到j节点长度为k的路径的总数，可以看出来这正是我们想要的。所以我们可以计算对应的有向图去掉危险节点之后的邻接矩阵，这样可以保证我们计算出来的路径不会经过危险节点。之后在用fast pow计算邻接矩阵的N次方。假设输入的DNA子序列有m个，平均长度为k，建立AC自动机的时间复杂度为O(m * k)，求得邻接矩阵的时间复杂度为O(m * k)，用fast pow计算矩阵的k次方的时间为O((log n) * m^3 * k^3)，完整代码如下：