[数据结构与算法]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)