Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hamming Distance

By prodip_bsmrstu · 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.


Discussion

Statistics


51% Solution Ratio

EgorKulikovEarliest, Dec '19

Mujahid_2923Fastest, 0.1s

omar24Lightest, 7.9 MB

mahdi.hasnatShortest, 369B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.