题解

从左到右填写问号时，新填一个字符，最多会新增一次以当前位置结尾的匹配。问题是，判断这次匹配时，要记住前面多少信息？

如果模式长度为 $3$，记住最后两位就够了。新字符接上去，检查这三位是否等于模式，然后丢掉最前面一位，继续处理。

但模式长度为 $m$ 时，照搬这个办法会有 $2^{m-1}$ 种后缀，状态太多。需要把那些对后续匹配没有区别的后缀合在一起。

前面已经填好的部分，只需要留下一个 KMP 状态

假设已经填好一段字符串。未来一次匹配如果跨过当前位置，那么已经出现的那部分，必须同时是已填串的后缀、模式串 $t$ 的前缀。

因此我们记录最长的这种长度 $j$。更短的可用长度都在它的失配链上，不必另外记录。给定 $j$ 和新字符，就能确定匹配向前推进，还是沿失配链退回，也就能确定新的状态。

先求模式串的前缀函数 $\pi$。这里 $\pi[x]$ 表示 $t[0\ldots x]$ 的最长相同真前后缀长度。再预处理两张表。

• $go[j][b]$ 表示处在状态 $j$ 时填入字符 $b$，接下来到哪个状态。
• $gain[j][b]$ 表示这一步是否形成完整匹配，取值为 $0$ 或 $1$。

状态只保留 $0\ldots m-1$。匹配长度达到 $m$ 的瞬间先记一次贡献，再退回 $\pi[m-1]$。

匹配成功后不能直接清零。 已完成的匹配末尾，可能还保留着下一次匹配的开头。退回最长真前后缀，才能继续统计重叠出现。

实现转移表时按 $j$ 递增处理。字符匹配就把长度加一；失配且 $j>0$ 时，直接使用状态 $\pi[j-1]$ 对这个字符的转移。它比 $j$ 小，已经算过。字符集只有两种，整张表只需 $O(m)$ 时间，不能在每一格都重新沿长失配链跳一遍。

倒着算 DP，方便从前往后决定答案

先只考虑出现次数。记

$$f[i][j]=\text{已经填好前 }i\text{ 位、当前状态为 }j\text{ 时，剩下最多能新增的匹配次数}.$$

过去已经出现了多少次，不包含在这个状态的值里。我们只算后面的贡献。

填完全部 $n$ 位就没有后续贡献，所以 $f[n][j]=0$。从 $i=n-1$ 倒推，当前位置可以填的字符集合记为 $B_i$，则

$$f[i][j]=\max_{b\in B_i}\left(gain[j][b]+f[i+1][go[j][b]]\right).$$

问号处可以选 $0,1$，固定字符处只能选原来的字符。式子里的两部分分别是本次填字新增的匹配，以及从新状态继续往后能得到的匹配。

每个合法补全都有一个确定的下一位，转移把这些选择全试过了；同一个状态下，过去的其他细节不会影响以后。因此这样倒推就能求出最优次数，答案为 $f[0][0]$。

字典序不必放进 DP 里比较

有了后缀最优值，就能从左到右恢复字符串。

在位置 $i$、状态 $j$，如果允许填 $0$，并且

$$gain[j][0]+f[i+1][go[j][0]]=f[i][j],$$

说明填 $0$ 以后仍有办法达到最优次数，就选 $0$。只有填 $0$ 达不到最优值，或者原字符禁止填 $0$，才考虑 $1$。填完后更新状态，处理下一位。

这样做不会损失最优次数。字典序也最小，因为比较两个串时只看第一个不同的位置，而我们在每个位置都优先选择了仍能完成最优答案的较小字符。无需在每个 DP 状态保存或比较整条字符串。

DP 一共有 $(n+1)m$ 个状态，每个状态至多尝试两个字符；恢复只扫描一次字符串。总时间和空间都是 $O(nm)$，题目保证 $nm\le4\times10^6$，存整数 DP 表约需 16 MB。保留整张表是为了恢复答案，不要直接滚动掉后面的行。

部分分里的提示

$n\le18$ 的 10 分可以枚举全部问号，逐个窗口数匹配，再按次数和字典序比较。设问号数为 $q$，时间 $O(2^qnm)$，额外空间 $O(n)$。

没有问号的 8 分只需匹配计数。即便直接比较每个窗口，$O(nm)$ 也已经够用，额外空间 $O(1)$，输出串就是原串。上面的枚举程序也能处理它，所以这两档合计 18 分。

$m=1$ 的 12 分中，每个问号都填成模式的唯一字符即可。每个位置的贡献独立，能增加一次匹配的选择必须选，时间 $O(n)$，额外空间 $O(1)$。

$m\le3$ 的 20 分可以采用开头提到的短后缀状态。用二进制整数记录最后 $m-1$ 位，最多四种状态，仍按后缀 DP 和从左到右优先选零的方法恢复。开头字符不足 $m$ 个时不能统计匹配，不能把状态中补的零当成真实字符。时间与空间为 $O(n2^{m-1})$。这档提示的正是如何保存未来需要的后缀信息，再由 KMP 把一般情况的状态数压下来。

将这几种简化做法按条件组合，可以保证前四档的 50 分。

参考代码

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<int> pi(m);
    for (int i = 1; i < m; ++i) {
        int j = pi[i - 1];
        while (j && t[i] != t[j]) j = pi[j - 1];
        if (t[i] == t[j]) ++j;
        pi[i] = j;
    }
    vector<array<int, 2>> go(m), gain(m);
    for (int j = 0; j < m; ++j) for (int b = 0; b < 2; ++b) {
        char c = char('0' + b);
        int nxt;
        if (t[j] == c) nxt = j + 1;
        else if (j == 0) nxt = 0;
        else {
            go[j][b] = go[pi[j - 1]][b];
            gain[j][b] = gain[pi[j - 1]][b];
            continue;
        }
        gain[j][b] = (nxt == m);
        // Fall back to the longest proper border to retain overlapping matches.
        go[j][b] = (nxt == m ? pi[m - 1] : nxt);
    }
    vector<int> dp((size_t)(n + 1) * m, 0);
    auto at = [&](int i, int j) -> int& { return dp[(size_t)i * m + j]; };
    for (int i = n - 1; i >= 0; --i) for (int j = 0; j < m; ++j) {
        int best = -1;
        for (int b = 0; b < 2; ++b) if (s[i] == '?' || s[i] == char('0' + b))
            best = max(best, gain[j][b] + at(i + 1, go[j][b]));
        at(i, j) = best;
    }
    cout << at(0, 0) << '\n';
    int state = 0;
    for (int i = 0; i < n; ++i) for (int b = 0; b < 2; ++b) {
        if (s[i] != '?' && s[i] != char('0' + b)) continue;
        if (at(i, state) == gain[state][b] + at(i + 1, go[state][b])) {
            cout << char('0' + b);
            state = go[state][b];
            break;
        }
    }
    cout << '\n';
}