Reconstruire la sous-suite commune

let plsc_suite a b =
  let n = String.length a and m = String.length b in
  let dp = Array.make_matrix (n + 1) (m + 1) 0 in
  for i = 1 to n do
    for j = 1 to m do
      if a.[i - 1] = b.[j - 1] then dp.(i).(j) <- dp.(i - 1).(j - 1) + 1
      else dp.(i).(j) <-
        (if dp.(i - 1).(j) >= dp.(i).(j - 1) then dp.(i - 1).(j) else dp.(i).(j - 1))
    done
  done;
  let rec remonte i j =
    if i = 0 || j = 0 then []
    else if a.[i - 1] = b.[j - 1] then remonte (i - 1) (j - 1) @ [a.[i - 1]]
    else if dp.(i - 1).(j) >= dp.(i).(j - 1) then remonte (i - 1) j
    else remonte i (j - 1)
  in
  remonte n m

Après avoir rempli la table, on remonte depuis (n, m) : un caractère commun se trouve sur la diagonale (on le garde et l'on remonte en diagonale) ; sinon on suit la direction qui a fourni le maximum. On renvoie une liste de caractères (et non une chaîne — la construire caractère par caractère sort du programme, cf. chapitre 6).