CodeForce 608B Hamming Distance Sum

[题目传送门] -----------------------> http://www.codeforces.com/problemset/problem/608/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 $\text{[math]}$ , 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|.

Input

The first line of the input contains binary string a (1 ≤ |a| ≤ 200 000).

The second line of the input contains binary string b (|a| ≤ |b| ≤ 200 000).

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|.

Sample test(s)

Input

01
00111

Output

Input

0011
0110

Output

[思路]

　　细心发现就是将A串中的每一位分别与B串中的进行比较，不同就ans++ .

　　很容易想到两个for的暴力解法，可惜字符串长度最大都可以是200000 ，爆搜的复杂度高达 n^2.

　　再分析发现，枚举A串的每一个字符c，只要看B串中能遇到多少不同于这个c的字符数，直接相加即可。

　　所以定义一个preOne[MAX] 数组， preOne[i] 代表B串中从下标 i 开始到 sizeB － 1 的 1 出现的次数。

　　preZero[MAX]同理。

[代码]

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <vector>
 4 #include <map>
 5 #include <string>
 6 #include <string.h>
 7 #include <set>
 8 #include <algorithm>
 9 using namespace std;
10 #define MAX 200010
11 #define LL long long 
12 char A[MAX];
13 char B[MAX];
14 
15 int preOne[MAX];
16 int preZero[MAX];
17 
18 int main()
19 {
20     scanf("%s",A);
21     scanf("%s",B);
22     int sizeA = strlen(A);
23     int sizeB = strlen(B);
24     int sumOne = 0;
25     int sumZero = 0;
26     LL ans = 0;
27     if(sizeA == sizeB)
28     {
29         for(int i = 0 ; i < sizeA ; i++)
30         {
31             if(A[i] != B[i]) ans++;
32         }
33     }
34     else
35     {
36         for(int i = sizeB - 1 ; i >= 0 ; i--)
37         {
38             int temp = B[i] - '0';
39             if(temp == 0)
40             {
41                 sumZero++;
42             }
43             else
44             {
45                 sumOne++;
46             }
47             preZero[i] = sumZero;
48             preOne[i] = sumOne;
49         }
50 
51         for(int i = 0 ; i < sizeA ; i++)
52         {
53             int temp = A[i] - '0';
54             if(temp == 0)
55             {
56                 ans += preOne[i] - preOne[sizeB - sizeA + 1 + i];
57             }
58             else
59             {
60                 ans += preZero[i] - preZero[sizeB - sizeA + 1 + i];
61             }
62         }
63 
64     }
65     cout << ans << endl;
66     return 0;
67 
68 }