Mélange de deux chaînes

• $w(0,0)$ est vrai. Le dernier symbole $W[p+q-1]$ du préfixe vient soit de $T$ (il vaut alors $t_{p-1}$ et le reste est un mélange de $T[0:p-1]$ et $U[0:q]$), soit de $U$ :

$$w(p,q)=(p>0\wedge w(p-1,q)\wedge t_{p-1}=W[p+q-1])\vee (q>0\wedge w(p,q-1)\wedge u_{q-1}=W[p+q-1]).$$

static boolean melange(String T, String U, String W) {
    int m = T.length(), n = U.length();
    if (W.length() != m + n) return false;
    boolean[][] w = new boolean[m + 1][n + 1];
    w[0][0] = true;                                          // base
    for (int p = 0; p < m + 1; p++)
        for (int q = 0; q < n + 1; q++) {
            if (p > 0 && w[p - 1][q] && T.charAt(p - 1) == W.charAt(p + q - 1)) w[p][q] = true;
            if (q > 0 && w[p][q - 1] && U.charAt(q - 1) == W.charAt(p + q - 1)) w[p][q] = true;
        }
    return w[m][n];
}

Complexité $\Theta (mn)$.

acbd mélange de ab, cd : true
bacd mélange de ab, cd : false
aadbbcbcac mélange de aabcc, dbbca : true

• Le glouton prend successivement dans $T$, $T$, $U$, $T$, $U$, $T$, $U$, $T$ les huit premiers symboles aadbbcbc : il a épuisé $T$, il lui reste $U=\text{ca}$ à placer face à ac, et il échoue sur le a. Pourtant $W$ est un mélange (le programme répond true) : avec le découpage $T,T,U,T,U,T,U,U,U,T$, les sept premiers choix sont ceux du glouton, mais le huitième symbole, le c, devait venir de $U$. Le choix « $T$ ou $U$ » quand les deux conviennent ne peut pas se faire localement : la programmation dynamique essaie les deux.