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

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