有一類(lèi)動(dòng)態(tài)規(guī)劃（其中也包含遞推）問(wèn)題，要求滿足一些限制條件的字符串，這些限制條件是“需要含有某個(gè)子串”或“不能含有某個(gè)子串”，那么KMP、AC自動(dòng)機(jī)等就有大用了。

【例1】HDU3689
題意：字符集中有一些字符，給出每個(gè)字符的出現(xiàn)概率（它們的和保證為1），再給出一個(gè)子串B，求：任給一個(gè)長(zhǎng)度為N的字符串A（只能包含字符集中的字符），使得S是A的子串的概率。

求解這類(lèi)問(wèn)題首先要進(jìn)行補(bǔ)集轉(zhuǎn)化。因?yàn)樽哟赡苡兄丿B（比如"ababa"中就出現(xiàn)了兩個(gè)"aba"），所以先轉(zhuǎn)化為“求任給一個(gè)長(zhǎng)度為N的字符串A（只能包含字符集中的字符），使得B不是A的子串的概率”，然后再用1減去這個(gè)概率即為結(jié)果。
設(shè)F[i][j]為“在所有長(zhǎng)度為i的不出現(xiàn)B的字符串中，后綴與B的前綴匹配長(zhǎng)度為j（即該字符串的后綴與B的前綴的最大匹配長(zhǎng)度為j）的概率”，很顯然，F(xiàn)是由遞推得到了，關(guān)鍵是如何進(jìn)行狀態(tài)轉(zhuǎn)移？或者說(shuō)，在遞推過(guò)程中，哪些狀態(tài)可能成為F[i][j]的前趨狀態(tài)？
假設(shè)F[i-1][k]是F[i][j]的前趨狀態(tài)，也就是說(shuō)，在字符集中至少存在一個(gè)字符c，使得主串的第i位（最后一位）取c時(shí)，能夠從F[i-1][k]轉(zhuǎn)移到F[i][j]。這就需要求一個(gè)值S[k][c]，表示當(dāng)主串的后綴與B的前綴的（最大）匹配長(zhǎng)度為k時(shí)，在主串后再加上一個(gè)字符c，其匹配長(zhǎng)度會(huì)變成什么。舉例：設(shè)目前主串A'="abasab"，B="asabs"，其匹配長(zhǎng)度為4，若在A'后加上一個(gè)字符's'，則匹配長(zhǎng)度變?yōu)?，所以S[4]['s']=5，而若在A'后加上一個(gè)字符'a'，則匹配長(zhǎng)度會(huì)變成1，所以S[4]['a']=1。顯然S值和A前面的哪些字符是沒(méi)有關(guān)系的。
那么這個(gè)S值如何計(jì)算？其實(shí)可以發(fā)現(xiàn)，S和KMP算法中的nx數(shù)組神似，因此完全可以按照計(jì)算nx數(shù)組的辦法來(lái)計(jì)算S。具體來(lái)說(shuō)，先要對(duì)B作KMP自身匹配，求出其nx數(shù)組，然后，在求S[k][c]的時(shí)候，嘗試在B的第k位（由于B的下標(biāo)從0開(kāi)始所以B[k-1]）后加上字符c，看看會(huì)“回退”到哪里即可。代碼： 這里m是B的長(zhǎng)度。注意，當(dāng)i=m時(shí)，S[i][j]是無(wú)意義的，因?yàn)榍懊嬉呀?jīng)說(shuō)過(guò)了不能出現(xiàn)B。
在求出S值后就能求出F值了。對(duì)于狀態(tài)F[i][j]，若存在一個(gè)字符c使得x=S[i][c]（滿足0<=x<m），則F[i][j]是F[i+1][x]的前趨狀態(tài)。當(dāng)然，由于本題是求概率而不是求總數(shù)，且每個(gè)字符出現(xiàn)的概率還不一樣，所以轉(zhuǎn)移的時(shí)候，應(yīng)是將F[i+1][x]加上F[i][j]*P[c]（P[c]是字符c出現(xiàn)的概率），邊界：F[0][0]=1，F(xiàn)[0][1..m-1]均為0。
最終結(jié)果為1-∑F[N][0..m-1]。

代碼

【例2】PKU1625（URAL1158）
題意：給出一些子串，求長(zhǎng)度為N，各個(gè)字符都屬于給定的字符集的所有字符串中，不包含任何一個(gè)給出的子串的字符串個(gè)數(shù)（需要使用壓9位的高精度）。

本題顯然是【例1】的多子串形式，而用來(lái)解決多個(gè)字符串同時(shí)匹配的只有AC自動(dòng)機(jī)，那么如何在本題中使用AC自動(dòng)機(jī)求解呢？
觀察【例1】中的F[i][j]，可以想象一下，一個(gè)圖中有m個(gè)頂點(diǎn)，分別表示匹配長(zhǎng)度為0..(m-1)，然后不斷新加入的字符讓這些狀態(tài)在這些結(jié)點(diǎn)間不斷轉(zhuǎn)移（狀態(tài)轉(zhuǎn)移就是圖中的邊），這樣，F(xiàn)[i][j]就表示“階段i到達(dá)結(jié)點(diǎn)j上”。而AC自動(dòng)機(jī)是基于Trie（樹(shù)）的，其中有現(xiàn)成的結(jié)點(diǎn)，這就揭示了本題的狀態(tài)：
F[i][j]表示長(zhǎng)度為i的合法的字符串（就是滿足字符集限制且不包含任何一個(gè)給定子串）中，在匹配到最后一位（第i位）后，剛好到達(dá)結(jié)點(diǎn)j的字符串的個(gè)數(shù)。
同樣，S[k][c]表示“目前到達(dá)結(jié)點(diǎn)k，接下來(lái)的一個(gè)字符是c的時(shí)候，會(huì)到達(dá)哪個(gè)結(jié)點(diǎn)。在對(duì)所有的子串建立了自動(dòng)機(jī)之后，S值只要類(lèi)似地搞就能求出來(lái)了。然后F的轉(zhuǎn)移也就搞定了。
不過(guò)，本題要萬(wàn)分注意AC自動(dòng)機(jī)的一個(gè)BUG：在建立了自動(dòng)機(jī)以后，需要把所有本身不危險(xiǎn)（如果一個(gè)結(jié)點(diǎn)代表的字符串剛好是某一個(gè)給出的不能出現(xiàn)的子串，則該結(jié)點(diǎn)是危險(xiǎn)結(jié)點(diǎn)），但通過(guò)失敗指針不斷上溯能夠到達(dá)一個(gè)危險(xiǎn)結(jié)點(diǎn)的結(jié)點(diǎn)，也標(biāo)記為危險(xiǎn)結(jié)點(diǎn)，比如兩個(gè)子串是"abcde"和"bc"，則代表"abcd"的那個(gè)結(jié)點(diǎn)由于包含了"bc"所以也是危險(xiǎn)的。
此外，本題的輸入要注意，字符集的ASCII碼范圍是-128~127，所以必須用char而不是unsigned char，且由于可能包含空格所以必須用gets()而不是scanf()輸入，又因?yàn)镃/C++中木有負(fù)數(shù)下標(biāo)，因此在輸入之后還要轉(zhuǎn)化一下（加128）。

代碼

【例3】PKU3691
題意：給出一些子串和一個(gè)字符串A（其每個(gè)字符均屬于字符集{'A', 'C', 'G', 'T'}），求至少要改動(dòng)A的幾個(gè)字符（不能改成不屬于字符集的字符），使得它不包含任何一個(gè)給出的子串，若不管怎么改都不行，則結(jié)果為-1。

這就是真正的DP了。設(shè)F[i][j]為前i位，到達(dá)的結(jié)點(diǎn)為j，最少改動(dòng)的字符個(gè)數(shù)，則轉(zhuǎn)移方程為
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的實(shí)際下標(biāo)從1開(kāi)始。
求S數(shù)組的方法見(jiàn)【例2】

代碼

【例4】PKU3208
題意：含有連續(xù)的三個(gè)數(shù)字6的正整數(shù)，稱(chēng)為"beastly number"，求第P個(gè)（1<=P<=50000000）"beastly number"（其位數(shù)不會(huì)超過(guò)15位）。
（這題是本沙茶在PKU上至今為止，自己想出算法的AC人數(shù)最少的題）
本題其實(shí)是用不著KMP的，因?yàn)?666"這樣簡(jiǎn)單的子串……

思路：由于位數(shù)不會(huì)超過(guò)15位（后來(lái)發(fā)現(xiàn)最多只有10位），所以每個(gè)"beastly number"都可以看成一個(gè)長(zhǎng)度為15，字符集為['0'..'9']的字符串（注意是可以有前導(dǎo)0的，因?yàn)槲粩?shù)可能不足15位）A，整個(gè)過(guò)程也就是從高位（第0位）向低位（第14位）求出A的各位。

預(yù)處理：求出F[i][j]，表示若A的前i位已經(jīng)確定（其中不含"666"，準(zhǔn)確來(lái)說(shuō)是非末尾不含"666"），且前i位的末尾剛好有j個(gè)'6'（j的范圍是0到3）時(shí)，有多少個(gè)"beastly number"（注意，前i位既然已經(jīng)確定，就不可更改了，能夠決定的只有第i位的后面）。
顯然先要求出F0[i][j]表示有多少個(gè)不是"beastly number"。其遞推方程不好寫(xiě)，見(jiàn)代碼（其實(shí)也是很好理解的）。然后F[i][j]=10^14-i - F0[i][j]。

然后就是不斷調(diào)整邊界來(lái)構(gòu)造了。準(zhǔn)確來(lái)說(shuō)，設(shè)前i-1位已經(jīng)確定，現(xiàn)在要確定第i位，則枚舉第i位是0~9中的哪個(gè)值，然后求出滿足條件的最小的"beastly number"和最大的"beastly number"的名次（注意，名次是從1開(kāi)始的），看看P在不在其中，這樣就能確定了。嚴(yán)重注意：如果已確定的位數(shù)中已經(jīng)出現(xiàn)了"666"，接下來(lái)的就不用枚舉了，直接在后面接上P-L就行了，L為左邊界。

但是，為什么要把本題放在KMP的專(zhuān)題里面呢囧？因?yàn)槿绻@個(gè)子串不是"666"而是一些結(jié)構(gòu)復(fù)雜的東東比如"123131"這樣的，只有借助KMP算法了。這時(shí)，F(xiàn)[i][j]就表示 A的前i位已經(jīng)確定（非末尾不含這個(gè)子串），且其后綴與這個(gè)子串的前綴匹配長(zhǎng)度為j，有多少個(gè)"beastly number" ，轉(zhuǎn)移方程與前幾個(gè)例子類(lèi)似。

代碼

總結(jié)：
KMP算法和AC自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移性質(zhì)決定了它們?cè)谧址ヅ漕?lèi)DP問(wèn)題中的巨大作用。在實(shí)際應(yīng)用中，要注意靈活使用它們。此外，AC自動(dòng)機(jī)的那個(gè)BUG是一定要注意的。