Temirulan

double calc1(int ind, int suff) {
    if(ind == s) return 0;
    double &res = dp1[ind][suff];
    if(calced[ind][suff]) return res;
    res = 0;
    calced[ind][suff] = 1;
    for(int i = 0; i < 26; i++) {
        char c = char(i + 'A');
        if(cnt[i]) {
            double p = cnt[i] / (1.0 * k);
            if(c == b[suff]) {
                int cur = 0;
                int nsuff = suff;
                if(suff + 1 == sz(b)) {
                    cur = 1;
                    nsuff = get(b, b);
                } else {
                    cur = 0;
                    nsuff = suff+1;
                }
                res += p * (cur + calc1(ind+1, nsuff));
            } else {
                int cur = 0;
                string cursuff = "";
                if(suff) cursuff += b.substr(0, suff);
                cursuff += c;
                int nsuff = get(b, cursuff);
                res += p * calc1(ind+1, nsuff);
            }
        }
    }
    return res;
}

//here is string b is the target string
//cnt[i] - appearance of char i
//k - length of keyboard
//s - is the length of typing string
//get(string a, string b) - returns the maximum length of suffix of b which is prefix of a.