Vus the Cossack and Strings

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.