// smc.c

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

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

#define C1(i)   c1[(i) + 1]
#define C2(i)   c2[(i) + 1]
#define P1(i)   p1[(i) + 1]
#define P2(i)   p2[(i) + 1]


int estDansAlpha(Lettre a, Mot w, Longueur ell) {
   Mot u;

   u = strchr(w, a);
   return( u != NULL && u - w < ell);
}


SousMot smc(Mot x, Longueur m, Mot y, Longueur n) {
   int i, j, k, *c, *c1, *c2, *p, *p1, *p2;
   SousMot u, v;

   c2 = (int *)malloc((m + 2)*sizeof(int));
   if (c2 == NULL) error("smc");
   p1 = (int *)malloc((m + 2)*sizeof(int));
   if (p1 == NULL) error("smc");
   p2 = (int *)malloc((m + 2)*sizeof(int));
   if (p2 == NULL) error("smc");

   if (m == 1 && estDansAlpha(x[0], y, n))
      return(creerSousMot(x[0]));
   else if (n == 1 && estDansAlpha(y[0], x, m))
      return(creerSousMot(y[0]));
   else if (m <= 1 || n <= 1)
      return(NULL);
   c1 = smcColonne(x, m, y, n/2);

   for (i = -1; i <= m - 1; ++i)
      P1(i) = i + 1;
   for (j = n/2; j <= n - 1; ++j) {
      C2(-1) = 0;
      P2(-1) = 0;
      for (i = 0; i <= m - 1; ++i)
         if (x[i] == y[j]) {
            C2(i) = C1(i - 1) + 1;
            P2(i) = P1(i - 1);
         }
         else if (C1(i) > C2(i - 1)) {
            C2(i) = C1(i);
            P2(i) = P1(i);
         }
         else {
            C2(i) = C2(i - 1);
            P2(i) = P2(i - 1);
         }
      c = c1;
      c1 = c2;
      c2 = c;
      p = p1;
      p1 = p2;
      p2 = p;
   }
   k = P1(m - 1);
   u = smc(x, k, y, n/2);
   v = smc(x + k, m - k, y + n/2, n - n/2);
   return(concatenerSousMot(u, v));
}