题解 ： https://xiaoxiaoh.blog.csdn.net/article/details/104952823

一、内容

你现在需要设计一个密码 S，S需要满足：S的长度是 N；S只包含小写英文字母；S不包含子串 T    ；例如：ab和 abcde 是 abcde 的子串，abd 不是 abcde的子串。请问共有多少种不同的密码满足要求？由于答案会非常大，请输出答案模 109+7的余数。

输入格式

第一行输入整数N，表示密码的长度。第二行输入字符串T，T中只包含小写字母。

输出格式

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

数据范围

1≤N≤50,1≤|T|≤N，|T|是T的长度。

输入样例1：

2
a

输出样例1：

625

二、思路

三、代码

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 5005, MOD = 1e9+7;
int n, m, ne[N], netj[27][N], f[N][N];
char s[N];
void getNext() {
    ne[1] = 0;
    for (int i = 2, j = 0; i < m; i++) {
        while (j && s[i] != s[j + 1]) j = ne[j];
        if (s[i] == s[j + 1]) j++;
        ne[i] = j; 
    }
}
void init() {
    for (int k = 0; k < 26; k++) {
        for (int j = 0; j < m; j++) {
            int tj = j;
            char c = (char)(k + 'a');
            while (tj && c != s[tj + 1]) tj = ne[tj];
            if (c == s[tj + 1]) tj++;
            netj[k][j] = tj; //记录最终跳的位置 
        }
    }
}
int main() {
    scanf("%d%s", &n, s + 1);
    m = strlen(s + 1);
    getNext();
    init(); //预处理 
    f[0][0] = 1;
    //f[i][j] 代表匹配到i这个字符,匹配串位置为j的种数 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) { //枚举所有的状态
            for (int k = 0; k < 26; k++) {
//              char c = (char)('a' + k);
//              int tj = j;
//              while (tj && c != s[tj + 1]) tj = ne[tj];
//              if (c == s[tj + 1]) tj++; //最终会跳的位置
                int tj = netj[k][j]; 
                //由(i-1,j)的状态跳到 (i, tj)的状态 
                if (tj < m) f[i][tj] = (f[i][tj] + f[i - 1][j]) % MOD;      
            }   
        }
    } 
    int ans = 0;
    for (int j = 0; j < m; j++) ans = (ans + f[n][j]) % MOD;
    printf("%d", ans);
    return 0;
}