1052 设计密码（kmp + 状态机模型）

柔情只为你懂 2022-09-12 02:56 175阅读 0赞

**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/][https_www.acwing.com_problem_content_description_1054]

**2. 思路分析：**

这道题目感觉还是挺难的，因为它不像股票问题可以直接看出存在多少个状态，状态之间的转移感觉还是比较隐晦，这道题目其实存在t个状态，我们可以从上一个状态跳到下一个状态，下一个状态可以是"a" - "z"，当可以跳的时候我们跳转到下一个状态，我们可以定义一个二维数组dp，其中dp\[i\]\[j\]表示前i个字符并且匹配了T中的j个字符的方案数目，可以看成是从前i个字符的某个位置到第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)

[https_www.acwing.com_problem_content_description_1054]: https://www.acwing.com/problem/content/description/1054/