Compute and store frequencies for every index
void precompute ( string s , string K ) { int n = s . size ( ) ; for ( int i = 0 ; i < n - 1 ; i ++ ) { cnt [ i + 1 ] = cnt [ i ] + ( s . substr ( i , K . size ( ) ) == K ) ; } }