有一類動態規劃（其中也包含遞推）問題，要求滿足一些限制條件的字符串，這些限制條件是“需要含有某個子串”或“不能含有某個子串”，那么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的專題里面呢囧？因為如果這個子串不是"666"而是一些結構復雜的東東比如"123131"這樣的，只有借助KMP算法了。這時，F[i][j]就表示 A的前i位已經確定（非末尾不含這個子串），且其后綴與這個子串的前綴匹配長度為j，有多少個"beastly number" ，轉移方程與前幾個例子類似。

代碼

總結：
KMP算法和AC自動機的狀態轉移性質決定了它們在字符串匹配類DP問題中的巨大作用。在實際應用中，要注意靈活使用它們。此外，AC自動機的那個BUG是一定要注意的。