// smc-colonne.c

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

#include <stdio.h>
#include "chl.h"

#define C1(i)   c1[(i) + 1]
#define C2(i)   c2[(i) + 1]


int *smcColonne(Mot x, Longueur m, Mot y, Longueur n) {
   int i, j, *c, *c1, *c2;

   c1 = (int *)malloc((m + 2)*sizeof(int));
   if (c1 == NULL) error("smcColonne");
   c2 = (int *)malloc((m + 2)*sizeof(int));
   if (c2 == NULL) error("smcColonne");

   for (i = -1; i <= m - 1; ++i) C1(i) = 0;   // memset(c1, 0, (m + 1)*sizeof(int));
   for (j = 0; j <= n - 1; ++j) {
      C2(-1) = 0;
      for (i = 0; i <= m - 1; ++i)
         if (x[i] == y[j])
            C2(i) = C1(i - 1) + 1;
         else
            C2(i) = MAX(C1(i), C2(i - 1));
      c = c1;
      c1 = c2;
      c2 = c;
   }
   return(c1);
}