解法

这道题其实就是考察 KMP 算法中 Next 数组的使用。题意转换过来大致就是：

给定两个 01 串，构造一个长度跟第一个串相同且 1 的个数相同的串，且保证第二个串的出现次数最多，出现可以重叠。

可以重叠的话，我们可以考虑贪心：后缀如果能跟前缀重合，那么出现的次数就有可能会变多。求出 Next 数组便是求出最长重合前后缀。我们可以循环添加字串的后缀，同时判断是否需要填充多余的 1 或 0。这样就搞定了。

代码

// D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 501000;
string A, B;
int totA, totB, nxt[MAX_N];
void getNext(string str)
{
    string tmp = " " + str;
    for (int i = 2; i <= tmp.length() - 1; i++)
    {
        int j = nxt[i - 1];
        while (j && tmp[j + 1] != tmp[i])
            j = nxt[j];
        if (tmp[j + 1] == tmp[i])
            nxt[i] = j + 1;
        else
            nxt[i] = 0;
    }
}
int main()
{
    cin >> A >> B;
    getNext(B);
    for (int i = 0; i < A.length(); i++)
        totA += A[i] - '0';
    for (int i = 0; i < B.length(); i++)
        totB += B[i] - '0';
    if (A.length() < B.length() || totA < totB)
        cout << A, exit(0);
    A = " " + A, B = " " + B;
    int ans = A.length();
    for (int i = 1, j = 0; i < A.length(); i++)
    {
        if (totA && B[j + 1] == '1')
            totA--, A[i] = '1', j++;
        else if (B[j + 1] == '0')
            A[i] = '0', j++;
        else
        {
            ans = i;
            break;
        }
        if (j == B.length() - 1)
            j = nxt[j];
    }
    for (int i = ans; i < A.length(); i++)
        A[i] = '0';
    while (totA)
    {
        ans--;
        if (A[ans] == '1')
            totA++;
        A[ans] = '1', totA--;
    }
    cout << A.substr(1);
    return 0;
}