Hamming distance between two binary strings of equal length is the number of mismatches between every corresponding positions of the two strings.
Suppose A = “01001” and B = “11000” then the Hamming Distance between A and B is 2 because they only mismatch in position 1 and 5 (1- based indexing).
Now, you are given two string A and B of length n and m respectively. A and B contains only lowercase english letters.
You have to calculate the sum of hamming distance between every substring of length m of A and B
The first line will contain two integers’ n and m.
Then the second line will contain two strings, A of length n and B of length m.
1 <= n,m <= 106
Input | Output |
---|---|
5 3 ababa aba | 3 |
In the first sample case, HD(“aba, aba”) = 0, HD(“bab”, “aba”) = 3, HD(“aba”, ”aba”) = 0. Note: HD = Hamming Distance. |