← 返回题目列表

Codeforces · 608/B

B. 汉明距离总和

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

杰诺斯需要你的帮助。埼玉要求他解决以下编程问题:

某个字符串 s 的长度表示为 |s|。两个等长字符串 s 和 t 之间的汉明距离定义为 $$\sum_{i=1}^{|s|} |s_i - t_i|$$,其中 si 是 s 的第 i 个字符,ti 是 t 的第 i 个字符。例如,字符串“0011”和字符串“0110”之间的汉明距离为 |0 - 0| + |0 - 1| + |1 - 1| + |1 - 0| = 0 + 1 + 0 + 1 = 2。

给定两个二进制字符串 a 和 b,求 a 与长度为 |a| 的 b 的所有连续子串之间的汉明距离之和。

输入

输入的第一行包含二进制字符串 a (1 ≤ |a| ≤ 200 000)。

输入的第二行包含二进制字符串 b (|a| ≤ |b| ≤ 200 000)。

两个字符串都保证仅包含字符“0”和“1”。

输出

打印单个整数 - a 与长度为 |a| 的 b 的所有连续子串之间的汉明距离之和。

示例

输入 #1

01
00111

输出 #1

3

输入 #2

0011
0110

输出 #2

2

注意

对于第一个示例案例,b 有四个长度为 |a| 的连续子串:“00”、“01”、“11”和“11”。 “01”和“00”之间的距离是|0 - 0| + |1 - 0| = 1.“01”和“01”之间的距离是|0 - 0| + |1 - 1| = 0。“01”和“11”之间的距离是|0 - 1| + |1 - 1| = 1。最后一个距离计数两次,因为字符串“11”出现两次。这些编辑距离的总和为 1 + 0 + 1 + 1 = 3。

声明中描述了第二个示例案例。