安全密码设计问题

题目描述

你需要设计一个密码 S，该密码需要满足以下条件：

1. 密码长度恰好为 N
2. 密码仅包含小写英文字母（a-z）
3. 密码中不包含特定子串 T

子串定义：若字符串 T 是字符串 S 的连续子序列，则称 T 是 S 的子串。
例如：abc 和 abcde 都是 abcde 的子串，但 abd 不是 abcde 的子串。

由于可能的密码数量非常大，请输出结果对 10⁹+7 取模的值。

输入格式

• 第一行：整数 N，表示密码长度
• 第二行：字符串 T，表示禁止出现的子串

输出格式

一个正整数，表示满足条件的密码总数模 10⁹+7

数据范围

• 1 ≤ N ≤ 50
• 1 ≤ |T| ≤ N （|T| 表示字符串 T 的长度）

输入样例

样例1

2
a

样例1输出

625

解释：总共有 26²=676 种可能，排除包含"a"的密码（共51种），676-51=625

样例2

4
cbc

样例2输出

456924

解题提示

1. 考虑使用动态规划结合KMP算法
2. 状态设计应跟踪当前匹配禁止子串的程度
3. 时间复杂度应为 O(N×|T|×26)
4. 注意处理大数取模运算（10⁹+7）

题目来源

Indeed Tokyo 2019 校招笔试题

Indeed Tokyo 指的是全球领先的求职招聘平台 Indeed 在 东京（日本） 的分部或服务。Indeed 是一个专注于帮助求职者寻找工作机会、帮助企业发布招聘信息的平台，覆盖全球多个国家和地区，东京作为日本的经济中心，自然也是 Indeed 的重要市场之一。

补充说明：

1. 题目考察字符串匹配与动态规划的结合应用
2. 需要高效处理子串匹配状态转移
3. 示例清晰地展示了排除禁止子串后的计数逻辑
4. 模数 10⁹+7 是常见的大质数，用于避免整数溢出
5. 数据范围较小（N≤50）但需要考虑所有字母组合情况