← 返回题目列表

Codeforces · 1186/C

C. 哥萨克 Vus 和弦乐

中文机器翻译题面 查看原题

Vus the Cossack 有两个二进制字符串,即仅由“0”和“1”组成的字符串。我们将这些字符串称为 $$$a$$$ 和 $$$b$$$。已知 $$$|b| \leq |a|$$$,即$$$b$$$的长度至多是$$$a$$$的长度。

哥萨克考虑字符串 $$$a$$$ 中长度为 $$$|b|$$$ 的每个子串。我们称这个子字符串为$$$c$$$。他匹配 $$$b$$$ 和 $$$c$$$ 中的相应字符,然后计算两个字符串不同的位置数。我们称这个函数为$$$f(b, c)$$$。

例如,让 $$$b = 00110$$$,$$$c = 11000$$$。在这些字符串中,第一、第二、第三和第四位置是不同的。

哥萨克人 Vus 计算这样的子串 $$$c$$$ 的数量,使得 $$$f(b, c)$$$ 是偶数。

例如,令 $$$a = 01100010$$$ 且 $$$b = 00110$$$。 $$$a$$$ 有四个长度为 $$$|b|$$$ 的子字符串:$$$01100$$$、$$$11000$$$、$$$10001$$$、$$$00010$$$。

- $$$f(00110, 01100) = 2$$$;
- $$$f(00110, 11000) = 4$$$;
- $$$f(00110, 10001) = 4$$$;
- $$$f(00110, 00010) = 1$$$。

由于三个子串中 $$$f(b, c)$$$ 是偶数,所以答案是 $$$3$$$。

Vus 找不到大字符串的答案。这就是为什么他要求你帮助他。

输入

第一行包含一个二进制字符串 $$$a$$$ ($$$1 \leq |a| \leq 10^6$$$) — 第一个字符串。

第二行包含一个二进制字符串 $$$b$$$ ($$$1 \leq |b| \leq |a|$$$) — 第二个字符串。

输出

打印一个数字——答案。

示例

输入 #1

01100010
00110

输出 #1

3

输入 #2

1010111110
0110

输出 #2

4

注意

第一个示例在图例中进行了解释。

在第二个例子中,有五个子字符串满足我们的要求:$$$1010$$$、$$$0101$$$、$$$1111$$$、$$$1111$$$。