// ls-une-memoire-faible.c

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

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

void lsUneMemoireFaible(Mot x, Longueur m, int bonSuff[], Mot y, Longueur n) {
   int i, j, dec, mem, turbo;

   dec = 0;
   mem = 0;
   j = m - 1;
   while (j < n) {
      i = m - 1;
      while (i >= 0 && x[i] == y[j - m + 1 + i])
         if (i == m - dec)
            i -= (mem - 1);   // Saut
         else
            --i;
      signalerSi(i < 0);
      if (i < 0) {
         dec = bonSuff[0];
         mem = m - dec;
      }
      else {
         turbo = mem - m + 1 + i;
         if (turbo <= bonSuff[i]) {
            dec = bonSuff[i];
            mem = MIN(m - dec, m - i);
         }
         else {
            dec = MAX(turbo, m - 1 - i);
            mem = 0;
         }
      }
      j += dec;               // Décalage
   }
}