ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4981: 汉明距离和

内存限制：128 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：13 通过：7
提交提交记录统计Web Board

题目描述


Genos需要你的帮助。埼玉要求他解决以下编程问题：

某些字符串s的长度表示为|s|，定义汉明距离为两字符串间对应的字符差值绝对值的和，其中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的所有相邻子字符串之间的汉明距离之和。
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 si is the i-th character of s and ti 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|.

Input
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.
Output
Print a single integer− the sum of Hamming distances between a and all contiguous substrings of b of length |a|.
Examples
Input 
01
00111
Output 
3
Input 
0011
0110
Output 
2
Note
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.

输入格式

输入的第一行包含二进制字符串a（1≤|一个|≤200000)

输入的第二行包含二进制字符串b（|a|≤|（b）|≤200000).

输出格式

打印单个整数− a与长度为|a|的b的所有相邻子串之间的汉明距离之和。
Examples
Input 
01
00111
Output 
3
Input 
0011
0110
Output 
2

输入样例 复制 

01
00111

输出样例 复制 

3

数据范围与提示

对于第一个示例情况，有四个长度为|a|的连续子字符串b:“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。

分类标签