608B. Hamming Distance Sum

Posted on Edited on In

B. Hamming Distance Sum

Description

输入长度均 ≤2e5 的字符串 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’) 的和。

进阶：额外输入 k，计算 s 所有长为 k 的子串与 t 的所有长为 k 的子串的 D 之和。

Hints/Notes

  • think how each element contribute to the final result

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>

#include <fstream>

using namespace std;

istream &in = cin;
ostream &out = cout;

void solve(string a, string b) {
    int m = a.size(), n = b.size();
    long long res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = i; j < n - m + i + 1; j++) {
            res += abs(a[i] - b[j]);
        }
    }
    out << res << endl;
}

int main() {
    string a, b;
    in >> a >> b;
    solve(a, b);
    return 0;
}