```// 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));
}
```