有一類動態(tài)規(guī)劃（其中也包含遞推）問題，要求滿足一些限制條件的字符串，這些限制條件是“需要含有某個子串”或“不能含有某個子串”，那么KMP、AC自動機等就有大用了。
【例1】
HDU3689題意：字符集中有一些字符，給出每個字符的出現(xiàn)概率（它們的和保證為1），再給出一個子串B，求：任給一個長度為N的字符串A（只能包含字符集中的字符），使得S是A的子串的概率。
求解這類問題首先要進行補集轉(zhuǎn)化。因為子串可能有重疊（比如"ababa"中就出現(xiàn)了兩個"aba"），所以先轉(zhuǎn)化為“求任給一個長度為N的字符串A（只能包含字符集中的字符），使得
B不是A的子串的概率”，然后再用1減去這個概率即為結(jié)果。
設(shè)F[i][j]為“在所有長度為i的
不出現(xiàn)B的字符串中，后綴與B的前綴匹配長度為j（即該字符串的后綴與B的前綴的
最大匹配長度為j）的概率”，很顯然，F(xiàn)是由遞推得到了，關(guān)鍵是如何進行狀態(tài)轉(zhuǎn)移？或者說，在遞推過程中，哪些狀態(tài)可能成為F[i][j]的前趨狀態(tài)？
假設(shè)F[i-1][k]是F[i][j]的前趨狀態(tài)，也就是說，
在字符集中至少存在一個字符c，使得主串的第i位（最后一位）取c時，能夠從F[i-1][k]轉(zhuǎn)移到F[i][j]。這就需要求一個值S[k][c]，表示當主串的后綴與B的前綴的（最大）匹配長度為k時，在主串后再加上一個字符c，其匹配長度會變成什么。舉例：設(shè)目前主串A'="abasab"，B="asabs"，其匹配長度為4，若在A'后加上一個字符's'，則匹配長度變?yōu)?，所以S[4]['s']=5，而若在A'后加上一個字符'a'，則匹配長度會變成1，所以S[4]['a']=1。顯然S值和A前面的哪些字符是沒有關(guān)系的。
那么這個S值如何計算？其實可以發(fā)現(xiàn)，S和KMP算法中的nx數(shù)組神似，因此完全可以按照計算nx數(shù)組的辦法來計算S。具體來說，先要對B作KMP自身匹配，求出其nx數(shù)組，然后，在求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]是無意義的，因為前面已經(jīng)說過了不能出現(xiàn)B。
在求出S值后就能求出F值了。對于狀態(tài)F[i][j]，若存在一個字符c使得x=S[i][c]（滿足0<=x<m），則F[i][j]是F[i+1][x]的前趨狀態(tài)。當然，由于本題是求概率而不是求總數(shù)，且每個字符出現(xiàn)的概率還不一樣，所以轉(zhuǎn)移的時候，應是將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）
題意：給出一些子串，求長度為N，各個字符都屬于給定的字符集的所有字符串中，不包含任何一個給出的子串的字符串個數(shù)（需要使用壓9位的高精度）。
本題顯然是【例1】的多子串形式，而用來解決多個字符串同時匹配的只有AC自動機，那么如何在本題中使用AC自動機求解呢？
觀察【例1】中的F[i][j]，可以想象一下，一個圖中有m個頂點，分別表示匹配長度為0..(m-1)，然后不斷新加入的字符讓這些狀態(tài)在這些結(jié)點間不斷轉(zhuǎn)移（狀態(tài)轉(zhuǎn)移就是圖中的邊），這樣，F(xiàn)[i][
j]就表示“階段i到達結(jié)點j上”。而AC自動機是基于Trie（樹）的，其中有現(xiàn)成的結(jié)點，這就揭示了本題的狀態(tài)：F[i][j]表示長度為i的合法的字符串（就是滿足字符集限制且不包含任何一個給定子串）中，在匹配到最后一位（第i位）后，剛好到達結(jié)點j的字符串的個數(shù)。
同樣，S[k][c]表示“目前到達結(jié)點k，接下來的一個字符是c的時候，會到達哪個結(jié)點。在對所有的子串建立了自動機之后，S值只要類似地搞就能求出來了。然后F的轉(zhuǎn)移也就搞定了。
不過，本題要萬分注意AC自動機的一個BUG：在建立了自動機以后，需要把所有本身不危險（如果一個結(jié)點代表的字符串剛好是某一個給出的不能出現(xiàn)的子串，則該結(jié)點是危險結(jié)點），但通過失敗指針不斷上溯能夠到達一個危險結(jié)點的結(jié)點，也標記為危險結(jié)點，比如兩個子串是"abcde"和"bc"，則代表"abcd"的那個結(jié)點由于包含了"bc"所以也是危險的。
此外，本題的輸入要注意，字符集的ASCII碼范圍是-128~127，所以必須用char而不是unsigned char，且由于可能包含空格所以必須用gets()而不是scanf()輸入，又因為C/C++中木有負數(shù)下標，因此在輸入之后還要轉(zhuǎn)化一下（加128）。
代碼【例3】
PKU3691題意：給出一些子串和一個字符串A（其每個字符均屬于字符集{'A', 'C', 'G', 'T'}），求至少要改動A的幾個字符（不能改成不屬于字符集的字符），使得它不包含任何一個給出的子串，若不管怎么改都不行，則結(jié)果為-1。
這就是真正的DP了。設(shè)F[i][j]為前i位，到達的結(jié)點為j，最少改動的字符個數(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的實際下標從1開始。
求S數(shù)組的方法見【例2】
代碼【例4】
PKU3208題意：含有連續(xù)的三個數(shù)字6的正整數(shù)，稱為"beastly number"，求第P個（1<=P<=50000000）"beastly number"（其位數(shù)不會超過15位）。
（這題是本沙茶在PKU上至今為止，自己想出算法的AC人數(shù)最少的題）
本題其實是用不著KMP的，因為"666"這樣簡單的子串……
思路：由于位數(shù)不會超過15位（后來發(fā)現(xiàn)最多只有10位），所以每個"beastly number"都可以看成一個長度為15，字符集為['0'..'9']的字符串（注意是可以有前導0的，因為位數(shù)可能不足15位）A，整個過程也就是從高位（第0位）向低位（第14位）求出A的各位。
預處理：求出F[i][j]，表示若A的前i位已經(jīng)確定（其中不含"666"，準確來說是非末尾不含"666"），且前i位的末尾剛好有j個'6'（j的范圍是0到3）時，有多少個"beastly number"（注意，前i位既然已經(jīng)確定，就不可更改了，能夠決定的只有第i位的后面）。
顯然先要求出F0[i][j]表示有多少個不是"beastly number"。其遞推方程不好寫，見代碼（其實也是很好理解的）。然后F[i][j]=10
14-i - F0[i][j]。
然后就是不斷調(diào)整邊界來構(gòu)造了。準確來說，設(shè)前i-1位已經(jīng)確定，現(xiàn)在要確定第i位，則枚舉第i位是0~9中的哪個值，然后求出滿足條件的最小的"beastly number"和最大的"beastly number"的名次（注意，名次是從1開始的），看看P在不在其中，這樣就能確定了。嚴重注意：如果已確定的位數(shù)中已經(jīng)出現(xiàn)了"666"，接下來的就不用枚舉了，直接在后面接上P-L就行了，L為左邊界。
但是，為什么要把本題放在KMP的專題里面呢囧？
因為如果這個子串不是"666"而是一些結(jié)構(gòu)復雜的東東比如"123131"這樣的，只有借助KMP算法了。這時，F(xiàn)[i][j]就表示 A的前i位已經(jīng)確定（非末尾不含這個子串），且其后綴與這個子串的前綴匹配長度為j，有多少個"beastly number" ，轉(zhuǎn)移方程與前幾個例子類似。
代碼總結(jié)：
KMP算法和AC自動機的狀態(tài)轉(zhuǎn)移性質(zhì)決定了它們在字符串匹配類DP問題中的巨大作用。在實際應用中，要注意靈活使用它們。此外，AC自動機的那個BUG是一定要注意的。