Compute and store frequencies for every index
def precompute ( s , K ) : NEW_LINE INDENT n = len ( s ) NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT cnt [ i + 1 ] = cnt [ i ] NEW_LINE if s [ i : len ( K ) + i ] == K : NEW_LINE INDENT cnt [ i + 1 ] += 1 NEW_LINE DEDENT DEDENT DEDENT