Compute and store frequencies for every index
function precompute ( s , K ) { var n = s . length ; for ( var i = 0 ; i < n - 1 ; i ++ ) { cnt [ i + 1 ] = cnt [ i ] + ( s . substring ( i , i + K . length ) == K ) ; } }