Loading... # 题目描述 你现在需要设计一个密码 $S$，$S$ 需要满足： - $S$ 的长度是 $N$； - $S$ 只包含小写英文字母； - $S$ 不包含子串 $T$； 例如：$abc$ 和 $abcde$ 是 $abcde$ 的子串，$abd$ 不是$abcde$的子串。 请问共有多少种不同的密码满足要求？ 由于答案会非常大，请输出答案模$10^9+7$的余数。 # 输入 第一行输入整数$N$，表示密码的长度。 第二行输入字符串$T$，$T$中只包含小写字母。 # 输出 输出一个**正整数**，表示总方案数模 $10^9+7$后的结果。 # 解题思路 看到求方案数， 可以从动态规划的角度来考虑 从线性DP的角度来考虑问题发现， 当确定了前$i$个字母所对应的方案数后， 为了满足不包括字符串$T$的条件， 需要且仅需要后缀子串中不包括字符串$T$即可 因此可以考虑使用KMP进行模式串匹配 ## KMP算法回顾 KMP算法实际上是一个确定的有限状态机的识别过程， 初始状态为0状态， 终止状态为m状态， 其中m是模式串的长度 ### next数组的计算 - next数组预处理如下情况的状态转换函数： - 若当前字符和模式串的下一个字符（状态）不匹配时跳转到的状态 - 预处理方法： - 如果当前状态不是初始状态， 并且当前字符和模式串的下一个字符不匹配， 则跳转到模式串上一个已经匹配的位置重新匹配 - 如果匹配成功则指针右移， 准备匹配下一个字符 - 更新next数组 ### KMP过程 KMP过程类似于next数组的计算 - 如果当前状态不是初始状态， 并且当前字符和模式串的下一个字符不匹配， 则跳转到模式串上一个已经匹配的位置重新匹配 - 如果匹配成功则指针右移， 准备匹配下一个字符 - 到达终止状态证明匹配成功 ## 状态的定义 基于上面的KMP的回顾，思路如下： - 设模式串共有$m$个字母， 则总共有$m$个状态 - 对于目标串的第$i$位可能的字母有26种， 为从`a`到`z`的所有字母 - 当以第$i$位结尾的后缀子串中为目标串$T$时， 为不合法状态（即当KMP跳转到状态m） - 当以第$i$位结尾的后缀子串是$T$的前缀时， KMP顺序进入下一个状态 - 当以第$i$位结尾的后缀子串不是$T$的前缀时， KMP会根据next数组进行状态跳转 因此可以定义如下的状态模型 - 将总字符串按照位数分为$N$位， 每位具有$m+1$个状态， 其中前$m$个状态为合法状态 - 定义状态`dp[i][j]`为第$i$位状态为$j$的状态 - 初始化`dp[0][0]`为$1$ - 对于状态`dp[i - 1][j]`位置的上的所有可能的字母`c`， 利用NEXT数组寻找其可以转移到的$u$状态`dp[i][u]` - 更新状态数量`dp[i][u] += dp[i - 1][j]` # AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #define endl '\n' using namespace std; const int N = 2e5 + 10; const int mod = 1e9 + 7; int n; char T[N]; int dp[N][30]; int ne[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; cin >> T + 1; int m = strlen(T + 1); for(int i = 2, j = 0; i <= n; i ++) { while(j && T[i] != T[j + 1]) j = ne[j]; if(T[i] == T[j + 1]) j ++; ne[i] = j; } dp[0][0] = 1; for(int i = 1; i <= n; i ++) { for(int j = 0; j < m; j ++) { for(char c = 'a'; c <= 'z'; c ++) { int u = j; while(u && c != T[u + 1]) u = ne[u]; if(c == T[u + 1]) u ++; if(u < m) dp[i][u] = (dp[i][u] + dp[i - 1][j]) % mod; } } } int res = 0; for(int i = 0; i < m; i ++) res = (res + dp[n][i]) % mod; cout << res << endl; return 0; } ``` 最后修改：2025 年 02 月 06 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏