Vus the Cossack and Strings (Codeforces 1186C)
Tags: Math, implementation

Vus the Cossack has two binary strings, that is, strings that consist only of "0" and "1". We call these strings $$$a$$$ and $$$b$$$. It is known that $$$|b| \leq |a|$$$, that is, the length of $$$b$$$ is at most the length of $$$a$$$.The Cossack considers every substring of length $$$|b|$$$ in string $$$a$$$. Let's call this substring $$$c$$$. He matches the corresponding characters in $$$b$$$ and $$$c$$$, after which he counts the number of positions where the two strings are different. We call this function $$$f(b, c)$$$.For example, let $$$b = 00110$$$, and $$$c = 11000$$$. In these strings, the first, second, third and fourth positions are different.Vus the Cossack counts the number of such substrings $$$c$$$ such that $$$f(b, c)$$$ is even.For example, let $$$a = 01100010$$$ and $$$b = 00110$$$. $$$a$$$ has four substrings of the length $$$|b|$$$: $$$01100$$$, $$$11000$$$, $$$10001$$$, $$$00010$$$.  $$$f(00110, 01100) = 2$$$; $$$f(00110, 11000) = 4$$$; $$$f(00110, 10001) = 4$$$; $$$f(00110, 00010) = 1$$$. Since in three substrings, $$$f(b, c)$$$ is even, the answer is $$$3$$$.Vus can not find the answer for big strings. That is why he is asking you to help him.

Input: The first line contains a binary string $$$a$$$ ($$$1 \leq |a| \leq 10^6$$$) — the first string.The second line contains a binary string $$$b$$$ ($$$1 \leq |b| \leq |a|$$$) — the second string.

Output: Print one number — the answer.

Note: The first example is explained in the legend.In the second example, there are five substrings that satisfy us: $$$1010$$$, $$$0101$$$, $$$1111$$$, $$$1111$$$.

Sample Inputs:
01100010
00110

1010111110
0110

Sample Outputs:
3

4

Solution (Python):
def solve(a, b):
    len_a = len(a)
    len_b = len(b)
    bits_xored_subarr_a = 0
    bits_xored_b = 0
    for i in range(0, len_b):
        if a[i] == '1':
            bits_xored_subarr_a ^= 1
        if b[i] == '1':
            bits_xored_b ^= 1
    count = 0
    for i in range(len_b, len_a):
        if bits_xored_subarr_a == bits_xored_b:
            count += 1
        if a[i] == '1':
            bits_xored_subarr_a ^= 1
        if a[i - len_b] == '1':
            bits_xored_subarr_a ^= 1
    if bits_xored_subarr_a == bits_xored_b:
        count += 1
    return count
if __name__ == '__main__':
    a = input()
    b = input()
    print(solve(a, b))

Solution (Python):
""""""

def solve(a, b):
    len_a = len(a)
    len_b = len(b)
    bits_xored_subarr_a = 0
    bits_xored_b = 0
    for i in range(0, len_b):
        if a[i] == '1':
            bits_xored_subarr_a ^= 1
        if b[i] == '1':
            bits_xored_b ^= 1
    count = 0
    for i in range(len_b, len_a):
        if bits_xored_subarr_a == bits_xored_b:
            count += 1
        if a[i] == '1':
            bits_xored_subarr_a ^= 1
        if a[i - len_b] == '1':
            bits_xored_subarr_a ^= 1
    if bits_xored_subarr_a == bits_xored_b:
        count += 1
    return count
if __name__ == '__main__':
    a = input()
    b = input()
    print(solve(a, b))

Solution (Python):
import math

def main():
    a = input()
    b = input()
    c = a[:len(b)]
    cnt = 0
    cntd = 0
    ans = 0
    for i in c:
        if i == '1':
            cnt += 1
    for i in b:
        if i == '1':
            cntd += 1
    if cnt % 2 == cntd % 2:
        ans += 1
    for i in range(len(b), len(a)):
        if a[i] == '1':
            cnt += 1
        if a[i - len(b)] == '1':
            cnt -= 1
        if cnt % 2 == cntd % 2:
            ans += 1
    print(ans)
main()