La plus longue sous-suite commune : rendre le mot, pas sa longueur

On remonte la table $L$ depuis la case $(n,m)$, exactement comme on remonte celle du sac : On note table_plsc la fonction plsc du chapitre, modifiée pour rendre la table $L$ entière au lieu de sa seule dernière case.

(* Renvoie une plus longue sous-suite commune a u et v (le MOT).
   Precondition : la table l a ete remplie comme dans le chapitre.
   Complexite : Theta(n + m) apres le remplissage, qui coute Theta(nm). *)
let plsc_mot u v =
  let l = table_plsc u v in
  let b = Buffer.create 16 in
  let i = ref (String.length u) and j = ref (String.length v) in
  (* VARIANT : i + j, qui decroit strictement a chaque tour. *)
  while !i > 0 && !j > 0 do
    if u.[!i-1] = v.[!j-1] then begin
      Buffer.add_char b u.[!i-1]; decr i; decr j      (* lettre commune *)
    end else if l.(!i-1).(!j) >= l.(!i).(!j-1) then decr i
    else decr j
  done;
  let s = Buffer.contents b in
  String.init (String.length s) (fun k -> s.[String.length s - 1 - k])

Mesure :

PLSC PROGRAMME / GRAMMAIRE = 6, mot = GRAMME
PLSC ALGORITHME / LOGARITHME = 8, mot = LGRITHME

Trois remarques de méthode.

• Terminaison. Le variant est $i+j$ : chaque branche diminue $i$, ou $j$, ou les deux. La boucle fait au plus $n+m$ tours.
• Le mot sort à l'envers. On remonte de la fin vers le début ; il faut retourner le tampon. C'est la faute la plus fréquente sur cet exercice, et elle est silencieuse sur un palindrome.
• Le choix en cas d'égalité. Quand $L[i-1][j]=L[i][j-1]$, les deux directions mènent à une sous-suite de même longueur, mais pas au même mot. On en obtient une, jamais toutes. C'est la même situation qu'à l'exercice sur le sac : la table porte la valeur de l'optimum, pas l'ensemble des optima.