python/TangDou/AcWing/Statemachine/1052.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 55;
const int MOD = 1e9 + 7;

int n, ne[N];
int f[N][N];
char p[N];
int res;

int main() {
    scanf("%d %s", &n, p + 1); // 读入模式串,存入到p数组中，下标从1开始
    int m = strlen(p + 1);     // 模式串的长度,读到\0结束，会自动计算出p串的长度

    // kmp利用模式串求ne数组【模板】
    for (int i = 2, j = 0; i <= m; i++) {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
    }

    f[0][0] = 1; // 递推起点,文本串0个字符，模板串0个字符，此时，方案数是1，其它状态都是0种方案

    // 开始填充dp表,为什么i,j都要从0开始呢？这其实要先看一下状态转移方程f[i][j]出现在了方程中，而初始值是边界
    // f[0][0]=1,所以填表的时候，自然也就是从i=0,j=0开始才能使用上初始值
    for (int i = 0; i < n; i++)                        // 阶段
        for (int j = 0; j < m && j <= i; j++)          // 匹配长度,需要注意的是完成一个字符ch的匹配，则j++,所以，j的上限是m-1,以达到f[n][m]的最终状态
            for (char ch = 'a'; ch <= 'z'; ch++) {     // 准备填充的下一个字符ch
                int u = j;                             // 要退到哪里去呢？
                while (u && ch != p[u + 1]) u = ne[u]; // 不断回退，找到新起点
                if (ch == p[u + 1]) u++;               // 如果匹配下一个字符
                f[i + 1][u] = (f[i + 1][u] + f[i][j]) % MOD;
            }

    // 枚举源串长度是n, 模式串匹配度不足m的，累加
    for (int i = 0; i < m; i++) res = (res + f[n][i]) % MOD;

    cout << res << endl;
    return 0;
}