<—点个赞吧QwQ

宣传一下算法提高课整理

你现在需要设计一个密码 $S$，$S$ 需要满足：

• $S$ 的长度是 $N$；
• $S$ 只包含小写英文字母；
• $S$ 不包含子串 $T$；

例如：$abc$ 和 $abcde$ 是 $abcde$ 的子串，$abd$ 不是 $abcde$ 的子串。

请问共有多少种不同的密码满足要求？

由于答案会非常大，请输出答案模 $10^9+7$ 的余数。

输入格式

第一行输入整数N，表示密码的长度。

第二行输入字符串T，T中只包含小写字母。

输出格式

输出一个正整数，表示总方案数模 $10^9+7$ 后的结果。

数据范围

$1 \le N \le 50$,
$1 \le |T| \le N$，$|T|$是$T$的长度。

输入样例1：

2
a

输出样例1：

625

输入样例2：

4
cbc

输出样例2：

456924

思路

一道有趣的题，是 GT 考试 的弱化版。

考虑 DP，设 $f_{i,j}$ 表示前 $i$ 个字符中，且不存在 $T$，并且末尾与 $T$ 匹配了 $j$ 个字母的方案数。

不难得到 $f_{i+1,j}=f_{i,0}\times w_{0,j}+f_{i,1}\times w_{1,j}+\cdots$，其中 $w_{i,j}$ 表示总长度相邻的两个串中，将末尾部分与 $T$ 重复部分的长度从 $i$ 变成 $j$
的方案数，显然可以预处理。

简单提提预处理的部分：考虑一个串的后缀和另一个串的前缀进行匹配，不难想到 KMP，然后你就可以用 KMP 的 $ne$ 数组往前跳，因为 $ne$ 数组中存的下标一定满足前缀和后缀一样，所以这样做是对的。

当然你也可以暴力匹配，这里就不贴了。

代码

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 60,MOD = 1e9 + 7;
int n,m;
char str[N];
int ne[N];
LL f[N][N];
int main () {
    cin >> n >> str + 1;
    m = strlen (str + 1);
    for (int i = 2,j = 0;i <= m;i++) {
        while (j && str[i] != str[j + 1]) j = ne[j];
        if (str[i] == str[j + 1]) j++;
        ne[i] = j;
    }
    f[0][0] = 1;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            for (char k = 'a';k <= 'z';k++) {
                int u = j;
                while (u && str[u + 1] != k) u = ne[u];
                if (str[u + 1] == k) u++;
                if (u < m) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % MOD;
            }
        }
    }
    LL ans = 0;
    for (int i = 0;i < m;i++) ans = (ans + f[n][i]) % MOD;
    cout << ans << endl;
    return 0;
}