题目描述

难度分:$1500$

输入长度均$\leq 2 \times 10^5$的字符串$s$和$t$，只包含$0$和$1$。并且$t$的长度大于等于$s$的长度。

定义$D(a,b) = |a[0]-b[0]| + |a[1]-b[1]| + … + |a[n-1]-b[n-1]|$。

例如$D($0011$,$0110$) = |0-0| + |0-1| + |1-1| + |1-0| = 0 + 1 + 0 + 1 = 2$。

设$s$的长度为$n$，对于$t$的所有长为$n$的连续子串$t’$，计算$D(s,t’)$。

输出所有$D(s,t’)$的和。

输入样例$1$

01
00111

输出样例$1$

3

输入样例$2$

0011
0110

输出样例$2$

2

算法

贡献法

先预处理出前缀和数组$presum$，$presum[0][i]$表示前缀$s[1…i]$中$0$的数量，$presum[1][i]$表示前缀$s[1…i]$中$1$的数量。

然后遍历$i \in [1,m]$计算每个$t[i]$对答案的贡献，对于$i$位置，当$s$在$t$上滑窗时，$t[i]$可以对应到$s$串的位置是$[l,r]=[max(1,i-m+n),min(i,n)]$，分为以下两种情况：

1. 当$t[i]=$0时，它的贡献为$presum[1][r]-presum[1][l-1]$，因为只有和$s$中的字符不同时才会产生贡献。
2. 当$t[i]=$1时，它的贡献为$presum[0][r]-presum[0][l-1]$。

复杂度分析

时间复杂度

遍历一遍$s$串，预处理出前缀和数组$presum$，再遍历一遍$t$串求得答案。因此，算法整体的时间复杂度为$O(n+m)$。

空间复杂度

空间消耗就在于前缀和数组$presum$，关于$0$和$1$的前缀和数组各占$O(n)$的空间，算法整体的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
char s[N], t[N];
int presum[2][N];

int main() {
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    int n = strlen(s + 1), m = strlen(t + 1);
    for(int i = 1; i <= n; i++) {
        presum[0][i] = presum[0][i - 1] + (s[i] == '0'? 1: 0);
        presum[1][i] = presum[1][i - 1] + (s[i] == '1'? 1: 0);
    }

    function<int(int , int, int)> windowSum = [&](int tp, int l, int r) {
        return presum[tp][r] - presum[tp][l - 1];
    };

    long long ans = 0;
    for(int i = 1; i <= m; i++) {
        int d = t[i] - '0';
        ans += windowSum(1 - d, max(1, i - m + n), min(i, n));
    }
    printf("%lld\n", ans);
    return 0;
}