Hamming Distance

prodip_bsmrstu Replay of BSMRSTU Intra U...
Limits 1s, 512 MB

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

Input

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

Output

A single integer, the sum of hamming distance between every substring of length m of A and B .

Sample

InputOutput
5 3
ababa aba
3

In the first sample case, HD(“aba, aba”) = 0, HD(“bab”, “aba”) = 3, HD(“aba”, ”aba”) = 0.
So the answer is 0 + 3 + 0 = 3.

Note: HD = Hamming Distance.


Submit

Login to submit.

Statistics

51% Solution Ratio
EgorKulikovEarliest, Dec '19
Mujahid_2923Fastest, 0.1s
omar24Lightest, 7.9 MB
mahdi.hasnatShortest, 369B
Toph uses cookies. By continuing you agree to our Cookie Policy.