Vus the Cossack and Strings

题意翻译

给定两个由$0,1$构成的字符串$a$和$b$,其中$|b|\leq |a|.$ 对于$a$的某个长度为$|b|$的字串$c$,记对应位不同的字符数为$f(b, c).$ 如:当$b=00110,c=11000$时,$f(b, c) = 4,$其中第$1,2,3,4$位不同。 求所有$c$中$f(b,c)$为偶数的个数。

题目描述

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.

输入输出格式

输入格式


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.

输出格式


Print one number — the answer.

输入输出样例

输入样例 #1

01100010
00110

输出样例 #1

3

输入样例 #2

1010111110
0110

输出样例 #2

4

说明

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