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 $ .