习题

#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
vector<int> prefix(const string str) {
    int len = str.size();
    vector<int> nxt(len);
    for (int i = 2 ; i < len ; i++) {
        int j = nxt[i - 1];
        while (j && str[i] != str[j + 1]) {
            j = nxt[j];
        }
        if (str[i] == str[j + 1]) j++;
        nxt[i] = j;
    }
    return nxt;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    a = " " + a;
    b = " " + b;
    auto kmp = prefix(b);
    vector nxt(m + 1, vector(26, 0));
    for (int i = 1 ; i <= m + 1 ; i++) {
        for (int j = 0 ; j < 26 ; j++) {
            if (i <= m && b[i] == 'a' + j) {
                nxt[i - 1][j] = i;
            } else {
                nxt[i - 1][j] = nxt[kmp[i - 1]][j];
            }
        }
    }
    vector dp(n + 1, vector(m + 1, -100000000));
    dp[0][0] = 0;
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 0 ; j <= m ; j++) {
            if (a[i] == '?') {
                for (int k = 0 ; k < 26 ; k++) {
                    dp[i][nxt[j][k]] = max(dp[i][nxt[j][k]], dp[i - 1][j]);
                }
            } else {
                dp[i][nxt[j][a[i] - 'a']] = max(dp[i][nxt[j][a[i] - 'a']], dp[i - 1][j]);
            }
        }
        dp[i][m]++;
    }
    int mx = 0;
    for (int i = 0 ; i <= m ; i++) mx = max(mx, dp[n][i]);
    cout << mx;
    return 0;
}