1052 設計密碼（kmp + 狀态機模型）

1. 問題描述：

你現在需要設計一個密碼 S，S 需要滿足：

S 的長度是 N；

S 隻包含小寫英文字母；

S 不包含子串 T；

例如：abc 和 abcde 是 abcde 的子串，abd 不是 abcde 的子串。請問共有多少種不同的密碼滿足要求？由于答案會非常大，請輸出答案模 10 ^ 9 + 7 的餘數。

輸入格式

第一行輸入整數N，表示密碼的長度。第二行輸入字元串T，T中隻包含小寫字母。

輸出格式

輸出一個正整數，表示總方案數模 10 ^ 9 + 7 後的結果。

資料範圍

1 ≤ N ≤ 50，

1 ≤ |T| ≤ N，|T|是T的長度。

輸入樣例1：

2

a

輸出樣例1：

625

輸入樣例2：

4

cbc

輸出樣例2：

456924

來源：https://www.acwing.com/problem/content/description/1054/

2. 思路分析：

這道題目感覺還是挺難的，因為它不像股票問題可以直接看出存在多少個狀态，狀态之間的轉移感覺還是比較隐晦，這道題目其實存在t個狀态，我們可以從上一個狀态跳到下一個狀态，下一個狀态可以是"a" - "z"，當可以跳的時候我們跳轉到下一個狀态，我們可以定義一個二維數組dp，其中dp[i][j]表示前i個字元并且和T比對到第j位的方案數目（動态規劃一般的定義方式是考慮前i個....的...），因為涉及到比對子串是否在某個字元串中，是以我們可以使用kmp算法進行比對，kmp算法循環停下來的位置就是前i - 1個字元比對的子串長度u，這樣我們就可以計算出目前前i個字元比對子串中的u個字元的方案數目。使用三層循環枚舉即可，第一層循環枚舉目前字元串的長度，第二層循環枚舉前i個字元串中比對的子串個數，第三層循環枚舉可以跳到的下一個狀态。

3. 代碼如下：

if __name__ == '__main__':
    n = int(input())
    # 因為後面需要使用kmp算法是以需要前面添加一個空的字元這樣字元串的下标可以從1開始
    s = " " + input()
    m, mod = len(s) - 1, 10 ** 9 + 7
    dp = [[0] * (m + 1) for i in range(n + 1)]
    next = [0] * (m + 1)
    i, j = 2, 0
    # 求解next數組, next數組下标從1開始比較好處理
    while i < m:
        while j and s[i] != s[j + 1]: j = next[j]
        if s[i] == s[j + 1]: j += 1
        next[i] = j
        i += 1
    dp[0][0] = 1
    for i in range(n):
        for j in range(m):
            # 嘗試跳到目前第k個字母看能夠比對多少個字元
            for k in range(26):
                # c為目前的小寫字母
                c = chr(k + 97)
                u = j
                while u and s[u + 1] != c: u = next[u]
                if s[u + 1] == c: u += 1
                if u < m: dp[i + 1][u] = (dp[i + 1][u] + dp[i][j]) % mod
    res = 0
    for i in range(m):
        res = (res + dp[n][i]) % mod
    print(res)