每日一题 20250202 acwing 1052 设计密码

#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;
const int N = 55;
char P[N];
int ne[N];
int f[N][N];
int p = 1e9 + 7;
int n, m;
int main() {
    scanf("%d", &n);
    scanf("%s", P);
    // printf("%s", P);
    m = strlen(P);
    // printf("%d\n", m);
    // f[i, j] = f[i - 1, j - 1] + s[j];
    memset(ne, -1, sizeof ne);
    for (int i = 1, j = -1; i < m; i++) { // mistake m as n
        while (~j && P[j + 1] != P[i]) { // the index starts from 0
            j = ne[j];
        }
        if (P[j + 1] == P[i]) j++; // mov the cursor
        ne[i] = j;
    }
    // printf("%d\n", ne[0]);
    f[0][0] = 1;
    for (int i = 0; i <= n - 1; ++i) {
        for (int j = 0; j < m; ++j) { // do not include m;
            for (int k = 0; k < 26; ++k) {
                int jj = j - 1; // j - 1 is the initial state
                while (~jj && P[jj + 1] - 'a' != k) {
                    jj = ne[jj];
                }
                if (P[jj + 1] - 'a' == k) { // recover the initial state by jj + 1 + 1
                    // printf("%d %d %d %c %c\n", i, j, k, k + 'a', P[jj + 1]);
                    if (jj + 1 != m - 1)
                        f[i + 1][jj + 2] = (f[i + 1][jj + 2] + f[i][j]) % p;
                } else {
                    f[i + 1][0] = (f[i + 1][0] + f[i][j]) % p; // if no pattern matches
                    // printf("%d %d %d\n", i, j, k);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < m; ++i) {
        // printf("%d ", f[n][i]);
        ans = (ans + f[n][i]) % p;
    }
    // puts("");
    printf("%d\n", ans);
    return 0;
}

状态机模型，顺便复习下离散数学和编译。