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

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

链接

Codeforces 808G

题解

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

f(i, j) 表示 s 串的前 i 个字符,其后缀最长匹配到 t 串的前缀长度为 j t 串的最多匹配次数,刷表转移。

代码

#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;