AMSTRING : http://ww2.codechef.com/COOK33/problems/AMSTRING

First we try to analyze the first input ,

n= 3 , k=2 aba

abb

so,

(a )ba

(a )bb

It is the selection. (1 , 1 ) to (1 , 1). Similaryly

(a b)a * (a b a) * a(b)a *a(ba) * ab(a)

(a b)b * (a b a) * a(b)b *a(bb) * ab(b)

Here characters enclosed by first bracket means that we have selected these (LA, RA, LB, RB) and as their hamming distance is <=2 .

Now, we are looking for the solutions of la=k and lb=k+i , for all i=1,2,3....,n-1

that is ,

aba. .abb

By cutting down the both side, we can write it as,

a[ba].

.[ab]b

now , from two string ba and ab we can have 3 selsection (calculate your self)

similarly, calculate for, ab[a].. ..[a]ba

there is just a 1 selection,

Now, do the revese things, string a will be shifted and b will be fixed,

.[ab]a a[bb]. there is 3 solutions,

..[a]ba

ab[a]..

these is 1 selection.

So, total solution is : 6+3+1+3+1=14

Now, How to calculate this one faster ?

Mine was calculated ovearall N*N log2(N) , which is O(10^7).

in n^2 way we can fix start and end point of each string.

Now, just do a pre-calculation of mis-matched character ........ sum the value up to the end.

Now,just make a walk , for each index , make a binary search to get : "how far i can go having hamming distance <=K".

Summing up all these subproblem , you will get your desired answer.

My Accepted Solution : http://ww2.codechef.com/viewsolution/2066888

shovon