个人理解：\(f[i][j]\)已经构造出前i个字母（相当于走了n步），并且当前和T已经匹配到第j个字母的方案。
设m为字符串T的长度：
在本题中，根据\(kmp\)匹配的思想，j + 1如果可以和当前第i个字母相同，那么j可以跳到j + 1，否则，j就回退，跳到next[j]我们构造的字串无论如何不能与T中第m个字母匹配起来，即j的状态到了m，那就是不合法状态，因为一旦匹配，就说明T成为了S的一个字串，那么就不符合题意了。
所以对于j的状态，只能是0到m - 1，那么j与什么有关呢，可以发现，j只与当前i是哪个字符有关，而当前第i个字符可以取值为a-z。
结果，就是\(f[n][i] (i \in [0, m))\)的累加。
很神奇的一道题，把这个模型记一下。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 55, Mod = 1e9 + 7;
int f[N][N];
char str[N];
int match[N], n;
int main() {
cin >> n >> str + 1;
int m = strlen(str + 1);
for (int i = 2, j = 0; i <= n; i++) {
while (j && str[i] != str[j + 1]) j = match[j];
if (str[i] == str[j + 1]) j++;
match[i] = j;
}
f[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = ‘a‘; k <= ‘z‘; k++) {
int u = j;
while (u && str[u + 1] != k) u = match[u];
if (k == str[u + 1]) u++;
if (u < m) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % Mod; //表示从第i步可以走到第i + 1步
}
}
}
int res = 0;
for (int i = 0; i < m; i++) res = (res + f[n][i]) % Mod;
cout << res << endl;
return 0;
}