608B.md (1977B)
1 Source: https://codeforces.com/problemset/problem/608/B 2 3 B. Hamming Distance Sum 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Genos needs your help. He was asked to solve the following programming problem by Saitama: 22 23 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. 24 25 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*|. 26 27 Input 28 29 The first line of the input contains binary string *a* (1 ≤ |*a*| ≤ 200 000). 30 31 The second line of the input contains binary string *b* (|*a*| ≤ |*b*| ≤ 200 000). 32 33 Both strings are guaranteed to consist of characters '0' and '1' only. 34 35 Output 36 37 Print a single integer — the sum of Hamming distances between *a* and all contiguous substrings of *b* of length |*a*|. 38 39 Examples 40 41 Input 42 43 ``` 44 01 45 00111 46 ``` 47 48 Output 49 50 ``` 51 3 52 ``` 53 54 Input 55 56 ``` 57 0011 58 0110 59 ``` 60 61 Output 62 63 ``` 64 2 65 ``` 66 67 Note 68 69 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. 70 71 The second sample case is described in the statement.