杰诺斯需要你的帮助。埼玉要求他解决以下编程问题:
某个字符串 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。
声明中描述了第二个示例案例。