// un-plus-long-sous-mot-commun.c

// << Algorithmique du texte >>
// Maxime Crochemore, Christophe Hancart et Thierry Lecroq
// Vuibert, 2001.

#include <stdio.h>
#include "chl.h"
#include "sous-mot.h"

#define S(i,j)   s[((i) + 1)*(n + 1) + (j) +1]


SousMot unPlusLongSousMotCommun(Mot x, Longueur m, Mot y, Longueur n, int *s) {
   int i, j;
   SousMot z;

   z = NULL;
   i = m - 1;
   j = n - 1;
   while (i != -1 && j != -1)
      if (x[i] == y[j]) {
         z = ajouterAuDebutSousMot(z, x[i]);
         --i;
         --j;
      }
      else if (S(i - 1, j) > S(i, j - 1))
         --i;
      else
         --j;
   return(z);
}