详细请查看注释

也就干了一下午的题解！应该算是最好理解的了！

如果帮助到你，请点赞支持一下！

时间复杂度：$O(26n^3)$

参考代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55, mod = 1e9 + 7;

int n, ne[N], f[N][N];
char s[N];

/*
    KMP + 状态机：
        对于本题来说，要保证设计的密码中不包含子串T，我们可以想到KMP的目的--->快速找到子串出现的起始位置！
        因此对于本题的第三个要求，不能有子串T，即表示KMP算法中只要j走不到模板串的末尾就一定不包含子串T！


    1. 这也是一个状态机问题！对于状态机问题，我们首先要确定状态：
        状态就是：KMP中j来回可以跳到的位置！（即j可以取0 ~ m共m + 1种状态，入口就是0号位置）

    2. 考虑j可以跳的情况：会发现j可以跳的位置是完全由模式串i的位置决定的，i位置对应的字符可以取（a ~ z），因此
        对于i的每种选法，j都有一个唯一跳法使得i和j+1位置对应的字符相等！
    也就是说对于模板串的j对应的m + 1种状态，每种状态都有26种选法（a ~ z），因此：我们就可以建一个具有m + 1个点，
        每个点都有26条边的图！

    3. 我们可以从入口0号位置开始跳，跳到的每一个位置都是一个合法的字符串（注意：不能跳到m位置，跳到m位置就表示包含子串T了）

    4. 也就是说：每一个合法的字符串，都可以一一对应到一种KMP上的状态机的走法。
              反过来说：每一种合法的KMP走法，都一一对应一个合法的字符串！
              即：合法字符串的方案数等价于KMP的状态机走法数！我们只要计算统计KMP的j的走法数即可！

    因此：最终的答案就是从入口开始走，不走到m位置，一共走n步（设计的密码S的长度限制），一共有多少种不同的路线！

        具体来说：对于模式串i的每一种选法方案，都会对应模板串j的一种走法；j的每一种走法都会对应模式串i的一种选法的合法方案！

    --------------------------------------- DP分析 ---------------------------------------------------

    状态表示：f[i][j]表示 “已经” 枚举了第i个字母（或第i步），处于j状态（即KMP中j可以跳到的0 ~ m+1种位置状态）的方案数！
    状态计算：考虑f[i][j]是有哪个状态（记该状态为A）转移过来的（简而言之：就是当前状态的方案数是由各类A的方案数之和组成）
        设j状态是由u状态跳过来的，即
                    f[i][j] = f[i - 1][u]
        解释：当前第i步处于j状态自然是从第i-1步跳过来的，并且是从可以跳到j状态的u状态跳过来的！
        注意：对于第i步，由于i位置26种选法的不同，j状态是由KMP动态移动求得，可能会出现j状态多次指向同一个位置，
              所以，准确来说应该是：f[i][j] += f[i - 1][u]

        由于模式串我们是从0开始的（即枚举的模式串的每一个位置的选法的下标），而对于步数来说是从1开始的：
            因此，准确来说应该是：f[i + 1][j] += f[i][u]

        对应到下方代码：u状态是从j状态跳过来的，因此：f[i + 1][u] += f[i][j]

    分析完毕！


    最终答案：f[n][j]的和（j可取0,1,2 ... m-1）

*/

int main(){
    cin >> n >> s + 1;
    int m = strlen(s + 1);

    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;
    }

    // 初始化
    // 含义：已经走了0步（没有走）且处于状态0（初始状态）的方案数 ---> 为 1 ---> 处于入口初始状态也是一种合法方案！
    //       换一个方式理解（不一定正确，仅供参考）：该初始化是为了后续计算的正确性！
    f[0][0] = 1; 
    for(int i = 0; i < n; i ++) // 枚举步数为i + 1（枚举下标为i的字符，i从0开始）
        for(int j = 0; j < m; j ++) // 枚举j可以跳到的状态（0 ~ m共m种状态，必然不能跳到m）
            for(char k = 'a'; k <= 'z'; k ++){ // 枚举模式串i可以取的 a-z 26种状态！
                // 对于模式串i的每种选法，利用KMP找到j可以跳到的位置u
                int u = j;
                while(u && k != s[u + 1]) u = ne[u];
                if(k == s[u + 1]) u ++;
                // 只要没有跳到m及m之后就是合法方案
                if(u < m) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % mod;
            } 

    int res = 0;
    for(int i = 0; i < m; i ++) res = (res + f[n][i]) % mod;
    cout << res << endl;
    return 0;
}

优化一维复杂度降低到n^2

将建图部分抽取出来即可。。。！

时间复杂度：$O(26n^2)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55, mod = 1e9 + 7;

int n, ne[N], f[N][N], g[N][26];
char s[N];

int main(){
    cin >> n >> s + 1;
    int m = strlen(s + 1);

    // 求next数组
    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;
    }

    // 预处理建图
    for (int j = 0; j < m; j ++) {
        for (int k = 'a'; k <= 'z'; k ++) {
            int u = j;
            while (u && s[u + 1] != k) u = ne[u];
            if (s[u + 1] == k) ++u;
            g[j][k - 'a'] = u;
        }
    }

    // 转态计算
    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 = g[j][k - 'a'];
                if(u < m) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % mod;
            } 

    int res = 0;
    for(int i = 0; i < m; i ++) res = (res + f[n][i]) % mod;
    cout << res << endl;
    return 0;
}