Hamming Distance Sum (Codeforces 608B)
Tags: Others, combinatorics

Genos needs your help. He was asked to solve the following programming problem by Saitama:The length of some string s is denoted |s|. The Hamming distance between two strings s and t of equal length is defined as , where si is the i-th character of s and ti is the i-th character of t. For example, the Hamming distance between string "0011" and string "0110" is |0 - 0| + |0 - 1| + |1 - 1| + |1 - 0| = 0 + 1 + 0 + 1 = 2.Given two binary strings a and b, find the sum of the Hamming distances between a and all contiguous substrings of b of length |a|.

Input: The first line of the input contains binary string a (1 ≤ |a| ≤ 200 000).The second line of the input contains binary string b (|a| ≤ |b| ≤ 200 000).Both strings are guaranteed to consist of characters '0' and '1' only.

Output: Print a single integer — the sum of Hamming distances between a and all contiguous substrings of b of length |a|.

Note: For the first sample case, there are four contiguous substrings of b of length |a|: "00", "01", "11", and "11". The distance between "01" and "00" is |0 - 0| + |1 - 0| = 1. The distance between "01" and "01" is |0 - 0| + |1 - 1| = 0. The distance between "01" and "11" is |0 - 1| + |1 - 1| = 1. Last distance counts twice, as there are two occurrences of string "11". The sum of these edit distances is 1 + 0 + 1 + 1 = 3.The second sample case is described in the statement.

Sample Inputs:
01
00111

0011
0110

Sample Outputs:
3

2

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from math import *

def main():
    a = input()
    b = input()
    n = len(b) - len(a) + 1
    con = b[:n].count('0')
    ans = con if a[0] == '1' else n - con
    for i in range(1, len(a)):
        if b[i - 1] != b[n + i - 1]:
            con += 1 if b[i - 1] == '1' else -1
        ans += con if a[i] == '1' else n - con
    print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip()
Iarr = lambda : list(map(int, input().split()))
Sarr = lambda : list(map(str, input().split()))
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    (aa, bb, zz, oo) = (input(), input(), [0], [0])
    z = o = 0
    for c in bb:
        if c == '0':
            z += 1
        else:
            o += 1
        zz.append(z)
        oo.append(o)
    print(sum((oo[stop] - oo[start] if c == '0' else zz[stop] - zz[start] for (c, start, stop) in zip(aa, range(999999), range(len(bb) - len(aa) + 1, 999999)))))
if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    freq = {0: 0, 1: 0}
    a = input().strip()
    b = input().strip()
    n = len(a)
    m = len(b)
    res = 0
    k = m - n
    for i in range(k):
        freq[int(b[i])] += 1
    for i in range(k, m):
        freq[int(b[i])] += 1
        res += freq[int(a[i - k]) ^ 1]
        freq[int(b[i - k])] -= 1
    print(res)
    return

def main():
    solve()
if __name__ == '__main__':
    main()