算法1

(kmp状态机 + dp)

定义：
* f[i][j]代表字符串长度为i且状态机状态为j的方案数。
初始状态有f[0][0] = 1, f[0][1 ~ (m - 1)] = 0
* 状态转移方程为:
markdown学好了再写，具体参考代码，其实只要搞清楚转态定义了，后面的就不难了。

时间复杂度

O(26 * N * N)

参考文献

参考了这位大佬解答里面的点睛之笔，茅塞顿开。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 55, mod = 1e9 + 7;
int f[N][N], ne[N], trans[N][26];
char str[N];
int n;

int main()
{
    cin >> n >> str + 1; 
    int 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;
    }

    // 先预处理状态机所有可能的转移路径

    for (int i = 0; i < m; i++) {
        for (int j = 'a'; j <= 'z'; j++) {
            int t = i;
            while (t && str[t + 1] != j) t = ne[t];
            if (str[t + 1] == j) t++;
            trans[i][j - 'a'] = t;
        }
    }

    // f[i][j]代表字符串长度为i且状态机状态为j的方案数
    // 初始状态有f[0][0] = 1, f[0][1 ~ (m - 1)] = 0

    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 'a'; k <= 'z'; k++) {
                int t = trans[j][k - 'a'];
                if (t < m) {
                    f[i][t] = (f[i][t] + f[i - 1][j]) % mod;
                }
            }
        }
    }

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

    return 0;
}