Plus longue sous-suite commune

let plsc 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;
  dp.(n).(m)

La ligne 0 et la colonne 0 valent 0 (PLSC avec une chaîne vide). Diagonale +1 si les caractères coïncident, sinon maximum des deux voisins. Coût $\Theta (nm)$.