CodeForces - 608B

给 a, b 两个二进制字符串,求 a 串与所有 b 连续子串的汉明距离的和

统计字符串 b 的前缀和,计算 a 中每个字符对答案的贡献

#include <bits/stdc++.h>
using namespace std;
const int maxn = 300000;
char s1[maxn], s2[maxn];
int ze[maxn], on[maxn];
int main()
{
    scanf("%s %s", s1, s2);
    int n1 = strlen(s1);
    int n2 = strlen(s2);
    for (int i = 0; i < n2; i++)
    {
        i &&(ze[i] = ze[i - 1]);
        i &&(on[i] = on[i - 1]);
        if (s2[i] == '0')
            ze[i]++;
        if (s2[i] == '1')
            on[i]++;
    }
    long long ans = 0;
    for (int i = 0; i < n1; i++)
        if (s1[i] == '0')
            ans += on[i + n2 - n1] - on[i - 1];
        else if (s1[i] == '1')
            ans += ze[i + n2 - n1] - ze[i - 1];
    printf("%lld\n", ans);
}