2021-02-06 新增 【因懒时隔六个月再接触算法发现自己什么都不会了，重新学了一遍有了点新思考】

我们首先明确直接暴力枚举是肯定会TLE的
但我们枚举的形式是怎么样的呢？
我们假定我们已经枚举了i位，且前i位并没有构成子串T（那么我们能构成T的情况只会在i以后了，
假定我们S[i-j+1~i]==T[1~j]成立），我们需要在第i+1位继续枚举且想知道此时S与T的匹配程度：
枚举到第i+1位有三种情况
1.刚好形成子串T（舍去）
2.未形成子串T且S[i+1] == S[j+1]
3.未形成子串T且S[i+1] != S[j+1]
而在第二种情况中，我们没什么好说的，可以继续向后枚举
在第三种情况中，我们就需要知道我们将3->2时此刻S与T的匹配程度，而这就正好引出我们需要KMP来优化算法
而到这，我们也知道暴力枚举不可行，我们可以猜测能否用dp来解决问题
f[i][j]:S的前i位与T的前j位匹配的方案数（S[i-j+1~i] == T[1~j])
上面推导其实有点生硬了，完全是知道结果推原因
下面便是闫式DP思考方法

原文

闫式DP

C++代码

#include <bits/stdc++.h>

using namespace std;

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

int n;
string s, t;
int ne[N];
int f[N][N];
//f[i][j]表示串S前i位为与串T前j位匹配成功，第i位匹配到子串中位置位j时(S[i - j + 1 ~ i] == T[1 ~ j])的方案数

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> t;
    s = ' ' + t;
    int m = s.length() - 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;
    }

    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) { //假定S[i + 1]位为k，与T[j + 1]位进行匹配判断
                int jj = j;
                while (jj && k != s[jj + 1]) jj = ne[jj];
                if (k == s[jj + 1]) ++jj;
                //f[i + 1][jj]代表串S前i+1位与串前jj位匹配成功(S[i+1-jj+1~i+1] == T[1~jj])方案数
                if (jj < m) 
                    f[i + 1][jj] = (f[i + 1][jj] + f[i][j]) % mod;
                //f[i][j]可以通过i+1赋值为k到达f[i+1][jj]点（新增路径）
                //注:可能存在重边,因为j不同但ne[j]是相同的,并且k是相同的,所以此时
                //f[i][j1]和f[i][j2]跳到的位置是一样的(k相同,ne[j1]=ne[j2])
            }
        }
    }

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

    return 0;
}