有一类动态规划(其中也包含递推)问题,要求满足一些限制条件的字符串,这些限制条件是“需要含有某个子串”或“不能含有某个子串”,那么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,看看会“回退”到哪里即可。代码:
     int j = 0; nx[0= 0;
     re2(i, 
1, m) {
            
while (j && A[i] != A[j]) j = nx[j - 1];
            
if (A[i] == A[j]) j++;
            nx[i] 
= j;
     }
     re(i, m) re(k, SZ) {
           j 
= i;
           
while (j && A[j] != k + 97) j = nx[j - 1];
           
if (A[j] == k + 97) S[i][k] = ++j; else S[i][k] = 0;
     }
这里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】PKU1625URAL1158
题意:给出一些子串,求长度为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]=1014-i - F0[i][j]。

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

但是,为什么要把本题放在KMP的专题里面呢囧?因为如果这个子串不是"666"而是一些结构复杂的东东比如"123131"这样的,只有借助KMP算法了。这时,F[i][j]就表示 A的前i位已经确定(非末尾不含这个子串),且其后缀与这个子串的前缀匹配长度为j,有多少个"beastly number" ,转移方程与前几个例子类似。

代码

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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理