KMP、AC自动机在字符串匹配类动态规划问题中的应用

有一类动态规划（其中也包含递推）问题，要求满足一些限制条件的字符串，这些限制条件是“需要含有某个子串”或“不能含有某个子串”，那么KMP、AC自动机等就有大用了。

【例1】HDU3689
题意：字符集中有一些字符，给出每个字符的出现概率（它们的和保证为1），再给出一个子串B，求：任给一个长度为N的字符串A（只能包含字符集中的字符），使得S是A的子串的概率。

求解这类问题首先要进行补集转化。因为子串可能有重叠（比如"ababa"中就出现了两个"aba"），所以先转化为“求任给一个长度为N的字符串A（只能包含字符集中的字符），使得B不是A的子串的概率”，然后再用1减去这个概率即为结果。
设F[i][j]为“在所有长度为i的不出现B的字符串中，后缀与B的前缀匹配长度为j（即该字符串的后缀与B的前缀的最大匹配长度为j）的概率”，很显然，F是由递推得到了，关键是如何进行状态转移？或者说，在递推过程中，哪些状态可能成为F[i][j]的前趋状态？
假设F[i-1][k]是F[i][j]的前趋状态，也就是说，在字符集中至少存在一个字符c，使得主串的第i位（最后一位）取c时，能够从F[i-1][k]转移到F[i][j]。这就需要求一个值S[k][c]，表示当主串的后缀与B的前缀的（最大）匹配长度为k时，在主串后再加上一个字符c，其匹配长度会变成什么。举例：设目前主串A'="abasab"，B="asabs"，其匹配长度为4，若在A'后加上一个字符's'，则匹配长度变为5，所以S[4]['s']=5，而若在A'后加上一个字符'a'，则匹配长度会变成1，所以S[4]['a']=1。显然S值和A前面的哪些字符是没有关系的。
那么这个S值如何计算？其实可以发现，S和KMP算法中的nx数组神似，因此完全可以按照计算nx数组的办法来计算S。具体来说，先要对B作KMP自身匹配，求出其nx数组，然后，在求S[k][c]的时候，尝试在B的第k位（由于B的下标从0开始所以B[k-1]）后加上字符c，看看会“回退”到哪里即可。代码： 这里m是B的长度。注意，当i=m时，S[i][j]是无意义的，因为前面已经说过了不能出现B。
在求出S值后就能求出F值了。对于状态F[i][j]，若存在一个字符c使得x=S[i][c]（满足0<=x<m），则F[i][j]是F[i+1][x]的前趋状态。当然，由于本题是求概率而不是求总数，且每个字符出现的概率还不一样，所以转移的时候，应是将F[i+1][x]加上F[i][j]*P[c]（P[c]是字符c出现的概率），边界：F[0][0]=1，F[0][1..m-1]均为0。
最终结果为1-∑F[N][0..m-1]。

代码

【例2】PKU1625（URAL1158）
题意：给出一些子串，求长度为N，各个字符都属于给定的字符集的所有字符串中，不包含任何一个给出的子串的字符串个数（需要使用压9位的高精度）。

本题显然是【例1】的多子串形式，而用来解决多个字符串同时匹配的只有AC自动机，那么如何在本题中使用AC自动机求解呢？
观察【例1】中的F[i][j]，可以想象一下，一个图中有m个顶点，分别表示匹配长度为0..(m-1)，然后不断新加入的字符让这些状态在这些结点间不断转移（状态转移就是图中的边），这样，F[i][j]就表示“阶段i到达结点j上”。而AC自动机是基于Trie（树）的，其中有现成的结点，这就揭示了本题的状态：
F[i][j]表示长度为i的合法的字符串（就是满足字符集限制且不包含任何一个给定子串）中，在匹配到最后一位（第i位）后，刚好到达结点j的字符串的个数。
同样，S[k][c]表示“目前到达结点k，接下来的一个字符是c的时候，会到达哪个结点。在对所有的子串建立了自动机之后，S值只要类似地搞就能求出来了。然后F的转移也就搞定了。
不过，本题要万分注意AC自动机的一个BUG：在建立了自动机以后，需要把所有本身不危险（如果一个结点代表的字符串刚好是某一个给出的不能出现的子串，则该结点是危险结点），但通过失败指针不断上溯能够到达一个危险结点的结点，也标记为危险结点，比如两个子串是"abcde"和"bc"，则代表"abcd"的那个结点由于包含了"bc"所以也是危险的。
此外，本题的输入要注意，字符集的ASCII码范围是-128~127，所以必须用char而不是unsigned char，且由于可能包含空格所以必须用gets()而不是scanf()输入，又因为C/C++中木有负数下标，因此在输入之后还要转化一下（加128）。

代码

【例3】PKU3691
题意：给出一些子串和一个字符串A（其每个字符均属于字符集{'A', 'C', 'G', 'T'}），求至少要改动A的几个字符（不能改成不属于字符集的字符），使得它不包含任何一个给出的子串，若不管怎么改都不行，则结果为-1。

这就是真正的DP了。设F[i][j]为前i位，到达的结点为j，最少改动的字符个数，则转移方程为
F[i][j] = min{F[i-1][x] + (A[i] != c)}，c∈{'A', 'C', 'G', 'T'}，S[x][c]=j。边界：F[0][root]=0，其余的F[0][]=+∞，A的实际下标从1开始。
求S数组的方法见【例2】

代码

【例4】PKU3208
题意：含有连续的三个数字6的正整数，称为"beastly number"，求第P个（1<=P<=50000000）"beastly number"（其位数不会超过15位）。
（这题是本沙茶在PKU上至今为止，自己想出算法的AC人数最少的题）
本题其实是用不着KMP的，因为"666"这样简单的子串……

思路：由于位数不会超过15位（后来发现最多只有10位），所以每个"beastly number"都可以看成一个长度为15，字符集为['0'..'9']的字符串（注意是可以有前导0的，因为位数可能不足15位）A，整个过程也就是从高位（第0位）向低位（第14位）求出A的各位。

预处理：求出F[i][j]，表示若A的前i位已经确定（其中不含"666"，准确来说是非末尾不含"666"），且前i位的末尾刚好有j个'6'（j的范围是0到3）时，有多少个"beastly number"（注意，前i位既然已经确定，就不可更改了，能够决定的只有第i位的后面）。
显然先要求出F0[i][j]表示有多少个不是"beastly number"。其递推方程不好写，见代码（其实也是很好理解的）。然后F[i][j]=10^14-i - F0[i][j]。

然后就是不断调整边界来构造了。准确来说，设前i-1位已经确定，现在要确定第i位，则枚举第i位是0~9中的哪个值，然后求出满足条件的最小的"beastly number"和最大的"beastly number"的名次（注意，名次是从1开始的），看看P在不在其中，这样就能确定了。严重注意：如果已确定的位数中已经出现了"666"，接下来的就不用枚举了，直接在后面接上P-L就行了，L为左边界。

代码

总结：
KMP算法和AC自动机的状态转移性质决定了它们在字符串匹配类DP问题中的巨大作用。在实际应用中，要注意灵活使用它们。此外，AC自动机的那个BUG是一定要注意的。