Plus longue sous-chaîne commune

• Base : $c(p,0)=c(0,q)=0$. Hérédité : si $t_{p-1}=u_{q-1}$, le suffixe commun se prolonge, $c(p,q)=1+c(p-1,q-1)$ ; sinon aucun suffixe commun non vide, $c(p,q)=0$.
• Une sous-chaîne commune est un suffixe commun de deux préfixes : la longueur cherchée est ${\max }_{p,q}c(p,q)$, et si le maximum est atteint en $(p,q)$, la sous-chaîne est $T[p-c(p,q):p]$.

static String sousChaine(String T, String U) {
    int m = T.length(), n = U.length(), best = 0, fin = 0;
    int[][] Cc = new int[m + 1][n + 1];
    for (int p = 1; p < m + 1; p++)
        for (int q = 1; q < n + 1; q++) {
            Cc[p][q] = (T.charAt(p - 1) == U.charAt(q - 1)) ? 1 + Cc[p - 1][q - 1] : 0;
            if (Cc[p][q] > best) { best = Cc[p][q]; fin = p; } // meilleure sous-chaîne vue
        }
    return T.substring(fin - best, fin);
}

• La plus longue sous-chaîne commune à algorithmique et logarithme est rithm, de longueur $5$ (leur plsc, lgrithme, de longueur $8$, est plus longue mais n'est pas contiguë).

nom : T
valeurs : a l g o r i t h m i q u e
vert : 4..8

nom : U
valeurs : l o g a r i t h m e
vert : 4..8
legende : rithm, contiguë