「Codeforces 808G」Anthem of Berland - KMP + DP

发表于 | 分类于

给一个含有字母以及 ? 的 串和一个含有字母的 串，其中 ? 可以匹配任何字符，求 串最多匹配 串多少次。

链接

Codeforces 808G

题解

对 进行 KMP，用类似 AC 自动机的方法预处理出 串的前 个字符加上字符 后，其后缀最多能匹配 串多长的前缀。

设 表示 串的前 个字符，其后缀最长匹配到 串的前缀长度为 ， 串的最多匹配次数，刷表转移。

代码

#include <cstdio>
#include <cstring>
#include <vector>

const int MAXN = 1e5;

int main() {
    static char s[MAXN + 2], t[MAXN + 2];
    scanf("%s %s", s + 1, t + 1);

    int n = strlen(s + 1), m = strlen(t + 1);

    static int ch[MAXN + 1][26], fail[MAXN + 1];
    for (int i = 1; i <= m; i++) ch[i - 1][t[i] - 'a'] = i;
    for (int i = 1, k = 0; i <= m; i++) {
        if (i > 1) {
            while (k && t[k + 1] != t[i]) k = fail[k];
            if (t[k + 1] == t[i]) fail[i] = ++k;
            else fail[i] = 0;
            // printf("fail[%d] = %d\n", i, fail[i]);
        }

        for (int j = 0; j < 26; j++) {
            if (!ch[i][j]) {
                ch[i][j] = ch[fail[i]][j];
            }
        }
    }

    std::vector< std::vector<int> > f(n + 1, std::vector<int>(m + 1, -1));
    f[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            if (f[i][j] == -1) continue;
            // printf("f(%d, %d) = %d\n", i, j, f[i][j]);
            for (int c = s[i + 1] == '?' ? 0 : (s[i + 1] - 'a'); c < (s[i + 1] == '?' ? 26 : (s[i + 1] - 'a' + 1)); c++) {
                f[i + 1][ch[j][c]] = std::max(f[i + 1][ch[j][c]], f[i][j] + (ch[j][c] == m));
            }
        }
    }

    int ans = 0;
    for (int i = 0; i <= m; i++) ans = std::max(ans, f[n][i]);
    printf("%d\n", ans);
}