Hamming Distance Sum

题意翻译

### 题目描述 吉诺斯需要你的帮助。他被要求完成塞塔玛出的如下编程问题： 字符串 s 的长度被表示为 $\left|s\right|$。两个等长字符串 s 和 t 之间的“Hamming”距离被定义为 $\sum\limits_{i=1}^{\left|s\right|}\left|s_i-t_i\right|$，其中，$s_i$ 是字符串 s 的第 i 个字符，$t_i$ 是字符串 t 的第 i 个字符。 比如说，字符串“0011”和字符串“0110”之间的“Hamming”距离为 $\left|0-0\right|+\left|0-1\right|+\left|1-1\right|+\left|1-0\right|=0+1+0+1=2$。 给定两个字符串 a 和 b，找到字符串 a 和所有字符串 b 的长度为 $\left|a\right|$ 的子串之间的“Hamming”距离总和。 ### 输入格式 第一行输入二进制字符串 a（$1\leqslant\left|a\right|\leqslant200000$）。 第二行输入二进制字符串 b（$\left|a\right|\leqslant\left|b\right|\leqslant200000$）。 两个字符串均只包含字符“0”和“1”。 ### 输出格式 输出一个整数，即字符串 a 和所有字符串 b 的长度为 $\left|a\right|$ 的子串之间的“Hamming”距离总和。

题目描述

Genos needs your help. He was asked to solve the following programming problem by Saitama: The length of some string $ s $ is denoted $ |s| $ . The Hamming distance between two strings $ s $ and $ t $ of equal length is defined as , where $ s_{i} $ is the $ i $ -th character of $ s $ and $ t_{i} $ is the $ i $ -th character of $ t $ . For example, the Hamming distance between string "0011" and string "0110" is $ |0-0|+|0-1|+|1-1|+|1-0|=0+1+0+1=2 $ . Given two binary strings $ a $ and $ b $ , find the sum of the Hamming distances between $ a $ and all contiguous substrings of $ b $ of length $ |a| $ .

输入输出格式

输入格式

The first line of the input contains binary string $ a $ ( $ 1<=|a|<=200000 $ ). The second line of the input contains binary string $ b $ ( $ |a|<=|b|<=200000 $ ). Both strings are guaranteed to consist of characters '0' and '1' only.

输出格式

Print a single integer — the sum of Hamming distances between $ a $ and all contiguous substrings of $ b $ of length $ |a| $ .

输入输出样例

输入样例 #1

01
00111

输出样例 #1

3

输入样例 #2

0011
0110

输出样例 #2

2

说明

For the first sample case, there are four contiguous substrings of $ b $ of length $ |a| $ : "00", "01", "11", and "11". The distance between "01" and "00" is $ |0-0|+|1-0|=1 $ . The distance between "01" and "01" is $ |0-0|+|1-1|=0 $ . The distance between "01" and "11" is $ |0-1|+|1-1|=1 $ . Last distance counts twice, as there are two occurrences of string "11". The sum of these edit distances is $ 1+0+1+1=3 $ . The second sample case is described in the statement.