CF608B.Hamming Distance Sum

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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.

首页