A10095. Hamming Distance Sum
编程题
普及/提高-
知识点
题目描述
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 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.
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.
The second sample case is described in the statement.