Compute and store frequencies for every index
static void precompute ( string s , string K ) { int n = s . Length ; for ( int i = 0 ; i < n - 2 ; i ++ ) { cnt [ i + 1 ] = cnt [ i ] ; if ( s . Substring ( i , K . Length ) . Equals ( K ) ) { cnt [ i + 1 ] += 1 ; } } cnt [ n - 2 + 1 ] = cnt [ n - 2 ] ; }