// Mot.java

import java.util.Enumeration;
import java.util.Vector;

/**
 * Classe permettant de manipuler des mots
 * @see     Lettre
 * @author  Maxime Crochemore
 * @author  Christophe Hancart
 * @author  Thierry Lecroq
 */
public class Mot {
   /** Un mot est un tableau de lettres */
   private Lettre[] mot;
   /** La longueur d'un mot est son nombre de lettres */
   private int longueur;

   /** Construit un mot vide */
   Mot() {
      this.longueur = 0;
      this.mot = new Lettre[0];
   }

   /** Construit un mot à partir d'un objet String */
   Mot(String mot) {
      this.longueur = mot.length();
      this.mot = new Lettre[this.longueur];
      for (int i = 0; i < this.longueur; ++i)
         this.mot[i] = new Lettre(mot.charAt(i));
   }

   /** Construit un mot ne contenant  qu'une seule lettre */
   Mot(Lettre a) {
      this.longueur = 1;
      this.mot = new Lettre[1];
      this.mot[0] = a;
   }

   /** Retourne le tableau de lettres du mot */
   public Lettre[] getMot() {
      return this.mot;
   }

   /** Fixe la valeur du tableau de lettres */
   private void setMot(Lettre[] mot) {
      this.mot = mot;
   }

   /** Retourne la longueur du mot */
   public int getLongueur() {
      return this.longueur;
   }

   /** Fixe la longueur du mot */
   private void setLongueur(int longueur) {
      this.longueur = longueur;
   }

   public String toString() {
      String resultat = "";
      for (int i = 0; i < this.longueur; i++)
         resultat = resultat + this.lettreA(i);
      return resultat;
   }

   boolean egal(int j, Mot x) {
      for (int i = 0; i < x.getLongueur(); ++i)
         if (!this.lettreA(i + j).equals(x.lettreA(i)))
            return false;
      return true;
   }

   /** Retourne la lettre à une position */
   Lettre lettreA(int i) {
      return this.mot[i];
   }

   public Object clone() {
      Mot w = new Mot();

      w.mot = (Lettre [])this.mot.clone();
      w.longueur = this.getLongueur();
      return w;
   }

   /** Teste si la lettre apparait dans le mot */
   public boolean contient(Lettre a) {
      int m = this.getLongueur();

      for (int i = 0; i <= m - 1; ++i)
         if (this.lettreA(i).equals(a))
            return true;
      return false;
   }

   /** Ajoute la lettre en premiere position et decale les autres */
   public void ajouterAuDebut(Lettre a) {
      int m = this.getLongueur();
      Lettre[] w = new Lettre[m + 1];

      System.arraycopy(this.mot, 0, w, 1, m);
      w[0] = a;
      this.mot = w;
      this.longueur = m + 1;
   }

   public Mot getLettres(int i, int j) {
      Mot x = new Mot();
      try {
         int ell = j - i + 1;
         Lettre[] mot = new Lettre[ell];
         System.arraycopy(this.mot, i, mot, 0, ell);
         x.setLongueur(ell);
         x.setMot(mot);
      }
      catch (Exception e) {}
      return x;
   }

   public Mot concat(Mot y) {
      int m = this.getLongueur(), n = y.getLongueur();
      Lettre[] mot = new Lettre[m + n];

      System.arraycopy(this.mot, 0, mot, 0, m);
      System.arraycopy(y.getMot(), 0, mot, m, n);
      Mot x = new Mot();
      x.setLongueur(m + n);
      x.setMot(mot);
      return x;
   }

   /**
    * Recherche naive
    * @param x  le mot à rechercher
    */
   public Vector localiserNaivement(Mot x) {
      Vector v = new Vector();
      int m, n;

      m = x.getLongueur();
      n = this.getLongueur();
      for (int j = 0; j <= n - m; ++j)
         if (this.egal(j, x))
            v.addElement(new Integer(j));
      return v;
   }

   /**
    * Calcule la table de dernière occurrence
    */
   public int[] derniereOccurrence(Alphabet alphabet) {
      int[] dernOcc;
      int m;

      m = this.getLongueur();
      dernOcc = new int[alphabet.getCard()];
      Enumeration e = alphabet.elements();
      while (e.hasMoreElements())
         dernOcc[alphabet.rang((Lettre)e.nextElement())] = m;
      for (int k = 0; k <= m - 2; ++k)
         dernOcc[alphabet.rang(this.lettreA(k))] = m - 1 - k;
      return dernOcc;
   }

   /**
    * Appelle le calcul de la table de dernière occurrence et
    * recherche rapide
    */
   public Vector localiserRapidement(Mot x, Alphabet alphabet) {
      Vector v = new Vector();
      int[] dernOcc = x.derniereOccurrence(alphabet);
      int m, n;

      m = x.getLongueur();
      n = this.getLongueur();
      for (int j = m - 1; j < n; j += dernOcc[alphabet.rang(this.lettreA(j))])
         if (this.egal(j - m + 1, x))
            v.addElement(new Integer(j - m + 1));
      return v;
   }

   public Vector localiserMotsCourts(EnsembleDeMots x, Alphabet alphabet) {
      Vector v = new Vector();
      PetitAutomate pA = x.petitAutomate(alphabet);
      int init = pA.getInit();
      int[] masq = pA.getMasq();
      int term = pA.getTerm();
      int r = 0;
      int n = this.getLongueur();

      for (int j = 0; j < n; ++j) {
         r = (init | (r << 1)) & masq[alphabet.rang(this.lettreA(j))];
         if ((r & term) != 0)
            v.addElement(new Integer(j));
      }
      return v;
   }

   public int[] bords() {
      int m = this.getLongueur();
      int[] bord = new int[m];
      int i = 0;

      for (int j = 1; j <= m - 1; ++j) {
         bord[j - 1] = i;
         while (i >= 0 && ! this.lettreA(j).equals(this.lettreA(i)))
            if (i == 0)
               i = -1;
            else
               i = bord[i - 1];
         ++i;
      }
      bord[m - 1] = i;
      return bord;
   }

   public int[] prefixes() {
      int m = this.getLongueur();
      int[] pref = new int[m];
      int g = 0, f = 0;

      pref[0] = m;
      for (int i = 1; i <= m - 1; ++i)
         if (i < g && pref[i - f] < g - i)
            pref[i] = pref[i - f];
         else {
            if (i > g) g = i;
            f = i;
            while (g < m && this.lettreA(g).equals(this.lettreA(g - f)))
               ++g;
            pref[i] = g - f;
         }
      return pref;
   }

   public int[] bonPrefixe() {
      int m = this.getLongueur();
      int[] bonPref = new int[m + 1];
      int i = 0;

      bonPref[0] = -1;
      for (int j = 1; j <= m - 1; ++j) {
         // Ici, mot[0..i-1] = Bord(mot[0..j-1])
         bonPref[j] = i;
         while (i >= 0 && ! this.lettreA(j).equals(this.lettreA(i)))
            i = bonPref[i];
         ++i;
      }
      bonPref[m] = i;
      return bonPref;
   }

   public int[] meilleurPrefixe() {
      int m = this.getLongueur();
      int[] meilPref = new int[m + 1];
      int i = 0;

      meilPref[0] = -1;
      for (int j = 1; j <= m - 1; ++j) {
         // Ici, mot[0..i-1] = Bord(mot[0..j-1])
         if (this.lettreA(j).equals(this.lettreA(i)))
            meilPref[j] = meilPref[i];
         else {
            meilPref[j] = i;
            do {
               i = meilPref[i];
            }
            while (i >= 0 && ! this.lettreA(j).equals(this.lettreA(i)));
         }
         ++i;
      }
      meilPref[m] = i;
      return meilPref;
   }

   public Vector localiserSelonPrefixe(Mot x, int[] pi) {
      Vector v = new Vector();
      int i = 0;
      int m = x.getLongueur();
      int n = this.getLongueur();

      for (int j = 0; j < n; ++j) {
         // Ici, x[0..i-1] est le plus long préfixe de x
         // qui est également un suffixe de y
         if (i == m)
            i = pi[m];
         while (i >= 0 && ! this.lettreA(j).equals(x.lettreA(i)))
            i = pi[i];
         ++i;
         if (i == m)
            v.addElement(new Integer(j - m + 1));
      }
      return v;
   }

   public Automate aluComplet(Alphabet alphabet) {
      Automate automate = new Automate();
      Etat q0 = automate.getInitial();
      Etat p, r, t;

      Enumeration e = alphabet.elements();
      while (e.hasMoreElements())
         q0.setCible((Lettre)e.nextElement(), q0);
      t = q0;
      for (int i = 0; i < this.getLongueur(); ++i) {
         p = new Etat();
         r = t.getCible(this.lettreA(i));
         t.setCible(this.lettreA(i), p);
         p.copieCibles(r);
         t = p;
      }
      t.setTerminal(true);
      return automate;
   }

   public Automate alpParDefault() {
      Automate automate = new Automate();
      Etat q0 = automate.getInitial(), p, r, t = q0;
      int m = this.getLongueur();

      for (int i = 0; i <= m - 1; ++i) {
         p = new Etat();
         r = t.getCible(this.lettreA(i));
         if (r == null)
            r = q0;
         t.setCible(this.lettreA(i), p);
         p.copieCibles(r);
         t = p;
      }
      t.setTerminal(true);
      return automate;
   }

   public Vector laDeterministe(Automate automate) {
      Etat r = automate.getInitial();
      Vector v = new Vector();
      int n = this.getLongueur();

      for (int j = 0; j <= n - 1; ++j) {
         r = r.getCible(this.lettreA(j));
         if (r.isTerminal())
            v.addElement(new Integer(j));
      }
      return v;
   }

   public Vector laDeterministeParSuppleance(EnsembleDeMots x, Alphabet
alphabet) {
      Automate automate = x.alpParSuppleance(alphabet);
      Etat r = automate.getInitial();
      Vector v = new Vector();
      int n = this.getLongueur();

      for (int j = 0; j <= n - 1; ++j) {
         r = r.cibleParSuppleance(automate, this.lettreA(j));
         if (r.isTerminal())
            v.addElement(new Integer(j));
      }
      return v;
   }

   public int[] suffixes() {
      int m = this.getLongueur();
      int suff[] = new int[m];
      int f = 0, g = m - 1;

      suff[m - 1] = m;
      for (int i = m - 2; i >= 0; --i)
         if (i > g && suff[i + m - 1 - f] < i - g)
            suff[i] = suff[i + m - 1 - f];
         else {
            if (i < g)
               g = i;
            f = i;
            while (g >= 0 && this.lettreA(g).equals(this.lettreA(g + m - 1 -
f)))
               --g;
            suff[i] = f - g;
         }
      return suff;
   }

   public int[] bonSuffixe(int[] suff) {
      int m = this.getLongueur();
      int bonSuff[] = new int[m];

      for (int i = m - 2, j = 0; i >= -1; --i)
         if (i == -1 || suff[i] == i + 1)
            while (j < m - 1 - i) {
               bonSuff[j] = m - 1 - i;
               ++j;
            }
      for (int i = 0; i <= m - 2; ++i)
         bonSuff[m - 1 - suff[i]] = m - 1 - i;
      return bonSuff;
   }

   public Vector lsSansMemoireFaible(Mot x, int[] bonSuff) {
      Vector v = new Vector();
      int m = x.getLongueur();
      int n = this.getLongueur();
      int i, j = m - 1;

      while (j < n) {
         i = m - 1;
         while (i >= 0 && x.lettreA(i).equals(this.lettreA(j - m + 1 + i)))
            --i;
         if (i < 0)
            v.addElement(new Integer(j));
         if (i < 0)
            j += bonSuff[0];
         else
            j += bonSuff[i];
      }
      return v;
   }

   public Vector lsSansMemoireFaibleLineaire(Mot x, int[] bonSuff) {
      Vector v = new Vector();
      int m = x.getLongueur();
      int n = this.getLongueur();
      int i, j = m - 1, ell = 0;

      while (j < n) {
         i = m - 1;
         while (i >= ell && x.lettreA(i).equals(this.lettreA(j - m + 1 + i)))
            --i;
         if (i < 0)
            v.addElement(new Integer(j));
         if (i < ell) {
            ell = m - bonSuff[0];
            j += bonSuff[0];
         }
         else {
            ell = 0;
            j += bonSuff[i];
         }
      }
      return v;
   }

   public Vector lsUneMemoireFaible(Mot x, int[] bonSuff) {
      Vector v = new Vector();
      int m = x.getLongueur();
      int n = this.getLongueur();
      int i, j = m - 1, dec = 0, mem = 0, turbo;

      while (j < n) {
         i = m - 1;
         while (i >= 0 && x.lettreA(i).equals(this.lettreA(j - m + 1 + i)))
            if (i == m - dec)
               i -= (mem - 1);   // Saut
            else
               --i;
         if (i < 0)
            v.addElement(new Integer(j));
         if (i < 0) {
            dec = bonSuff[0];
            mem = m - dec;
         }
         else {
            turbo = mem - m + 1 + i;
            if (turbo <= bonSuff[i]) {
               dec = bonSuff[i];
               mem = Math.min(m - dec, m - i);
            }
            else {
               dec = Math.max(turbo, m - 1 - i);
               mem = 0;
            }
         }
         j += dec;               // Décalage
      }
      return v;
   }

   public Vector lsPlusieursMemoiresFaible(Mot x, int[] suff, int[] bonSuff) {
      Vector v = new Vector();
      int m = x.getLongueur();
      int n = this.getLongueur();
      int i, j = m - 1, k, s;
      int[] skip = new int[n];

      j = m - 1;
      while (j < n) {
         i = m - 1;
         while (i >= 0)
            if (skip[j - m + 1 + i] > 0) {
               k = skip[j - m + 1 + i];
               s = suff[i];
               if (s != k) {
                  i -= Math.min(s, k);
                  break;
               }
               else
                  i -= k;   // Saut
            }
            else if (x.lettreA(i).equals(this.lettreA(j - m + 1 + i)))
               --i;
            else
               break;
         if (i < 0)
            v.addElement(new Integer(j));
         if (i < 0) {
            skip[j] = m;
            j += bonSuff[0];
         }
         else {
            skip[j] = m - 1 - i;
            j += bonSuff[i];
         }
      }
      return v;
   }

   public Couple rechercheSimple(Mot[] liste) {
      int d = -1, i, ell, m = this.getLongueur(), n = liste.length, f = n;

      while (d + 1 < f) {
         // Invariant : liste[d] < x < liste[f]
         i = (d + f)/2;
         ell = this.llpc(liste[i]);
         if (ell == m && ell == liste[i].getLongueur())
            return new Couple(new Integer(i), new Integer(i));
         else if (ell == liste[i].getLongueur() ||
                  (ell != m &&
                   liste[i].lettreA(ell).inferieurA(this.lettreA(ell))))
            d = i;
         else
            f = i;
      }
      return new Couple(new Integer(d), new Integer(f));
   }

   public int llpc(Mot y) {
      int i = 0, m = this.getLongueur(), n = y.getLongueur();

      while (i < m && i < n && this.lettreA(i).equals(y.lettreA(i)))
         ++i;
      return i;
   }

   public Automate arbreSuffixes() {
      Automate automate = new Automate();
      Couple couple;
      Etat fourche, p, q;
      int k, n = this.getLongueur();

      for (int i = 0; i <= n - 1; ++i) {
         couple = this.descLente(automate.getInitial(), i);
         fourche = (Etat)couple.getComp1();
         k = ((Integer)couple.getComp2()).intValue();
         p = fourche;
         for (int j = k; j <= n - 1; ++j) {
            q = new Etat();
            p.setCible(this.lettreA(j), q);
            p = q;
         }
         p.setSortie(i);
      }
      automate.getInitial().setSortie(n);
      return automate;
   }

   private Couple descLente(Etat p, int k) {
      int n = this.getLongueur();

      while (k < n && p.getCible(this.lettreA(k)) != null) {
         p = p.getCible(this.lettreA(k));
         ++k;
      }
      return new Couple(p, new Integer(k));
   }

   private Couple descLenteBis(Etat p, int k, Automate automate) {
      int n = this.getLongueur();
      Etat e, f, q;

      while (k < n && p.getCible(this.lettreA(k)) != null) {
         q = p.getCible(this.lettreA(k));
         e = p;
         f = q;
         while (e != automate.getInitial() && f.getLs() == null) {
            f.setLs(e.getLs().getCible(this.lettreA(k)));
            e = e.getLs();
            f = f.getLs();
         }
         if (e == automate.getInitial())
            f.setLs(automate.getInitial());
         p = q;
         ++k;
      }
      return new Couple(p, new Integer(k));
   }

   public Automate arbreSuffixesBis() {
      Automate automate = new Automate();
      Couple couple;
      Etat fourche = automate.getInitial(), p, q;
      int k = 0, n = this.getLongueur();

      automate.getInitial().setLs(automate.getInitial());
      for (int i = 0; i <= n - 1; ++i) {
         k = Math.max(k, i);
         couple = this.descLenteBis(fourche.getLs(), k, automate);
         fourche = (Etat)couple.getComp1();
         k = ((Integer)couple.getComp2()).intValue();
         p = fourche;
         for (int j = k; j <= n - 1; ++j) {
            q = new Etat();
            p.setCible(this.lettreA(j), q);
            p = q;
         }
         p.setSortie(i);
      }
      automate.getInitial().setSortie(n);
      return automate;
   }

   public Automate autoSuffixes() {
      Automate automate = new Automate();
      Etat p;
      int n = this.getLongueur();

      automate.getInitial().setL(0);
      automate.getInitial().setF(null);
      automate.setDernier(automate.getInitial());
      for (int i = 0; i <= n - 1; ++i)
         this.lettreA(i).extension(automate);
      p = automate.getDernier();
      do {
         p.setTerminal(true);
         p = p.getF();
      }
      while (p != null);
      return automate;
   }

   public Automate interdits(Automate sy, Alphabet alphabet) {
      Automate automate = new Automate();
      Couple couple;
      Etat p, pp, qp;
      File ell = new File();
      Lettre a;
      Vector atteint = new Vector();

      ell.enfiler(new Couple(sy.getInitial(), automate.getInitial()));
      atteint.addElement(sy.getInitial());
      while (!ell.estFileVide()) {
         couple = (Couple)ell.defilement();
         p = (Etat)couple.getComp1();
         pp = (Etat)couple.getComp2();
         Enumeration e = alphabet.elements();
         while (e.hasMoreElements()) {
            a = (Lettre)e.nextElement();
            if (p.getCible(a) == null &&
                (p == sy.getInitial() || p.getF().getCible(a) != null)) {
               qp = new Etat();
               qp.setTerminal(true);
               pp.setCible(a, qp);
            }
            else if (p.getCible(a) != null &&
                     !atteint.contains(p.getCible(a))) {
               qp = new Etat();
               pp.setCible(a, qp);
               ell.enfiler(new Couple(p.getCible(a), qp));
               atteint.addElement(p.getCible(a));
            }
         }
      }
      return automate;
   }

   public int[] longueurDesFacteurs(Automate sx) {
      Etat p = sx.getInitial();
      int ell = 0, n = this.getLongueur();
      int[] t = new int[n];

      for (int i = 0; i <= n - 1; ++i) {
         if (p.getCible(this.lettreA(i)) != null) {
            ++ell;
            p = p.getCible(this.lettreA(i));
         }
         else {
            do {
               p = p.getF();
            }
            while (p != null && p.getCible(this.lettreA(i)) == null);
            if (p != null) {
               ell = p.getL() + 1;
               p = p.getCible(this.lettreA(i));
            }
            else {
               ell = 0;
               p = sx.getInitial();
            }
         }
         t[i] = ell;
      }
      return t;
   }

   public Table calculGeneriqueBis(Mot y) {
      int m = this.getLongueur();
      int n = y.getLongueur();
      Table t = new Table(m, n);

      t.set(-1, -1, 0);
      for (int i = 0; i <= m - 1; ++i)
         t.set(i, -1, t.get(i - 1, -1) + this.lettreA(i).del());
      for (int j = 0; j <= n - 1; ++j)
         t.set(-1, j, t.get(-1, j - 1) + y.lettreA(j).ins());
      for (int j = 0; j <= n - 1; ++j)
         for (int i = 0; i <= m - 1; ++i)
            t.set(i, j,
             Math.min(
              t.get(i - 1, j - 1) + this.lettreA(i).sub(y.lettreA(j)),
              Math.min(
               t.get(i - 1, j) + this.lettreA(i).del(),
               t.get(i, j - 1) + y.lettreA(j).ins())));
      return t;
   }

   public int calculGenerique(Mot y) {
      Table t = this.calculGeneriqueBis(y);
      return t.get(this.getLongueur() - 1, y.getLongueur() - 1);
   }

   public Alignement unAlignement(Mot y, Table t) {
      Alignement z = new Alignement();
      int m = this.getLongueur(), n = y.getLongueur(), i = m - 1, j = n - 1;

      while (i != -1 && j != -1)
         if (t.get(i, j) == t.get(i - 1, j - 1) +
                            this.lettreA(i).sub(y.lettreA(j))) {
            z.ajouterAuDebut(this.lettreA(i), y.lettreA(j));
            --i;
            --j;
         }
         else if (t.get(i, j) == t.get(i - 1, j) + this.lettreA(i).del()) {
            z.ajouterAuDebut(this.lettreA(i), new Lettre('-'));
            --i;
         }
         else {
            z.ajouterAuDebut(new Lettre('-'), y.lettreA(j));
            --j;
         }
      while (i != -1) {
         z.ajouterAuDebut(this.lettreA(i), new Lettre('-'));
         --i;
      }
      while (j != -1) {
         z.ajouterAuDebut(new Lettre('-'), y.lettreA(j));
         --j;
      }
      return z;
   }

   public void lesAlignements(Mot y, Table t) {
      this.la(this.getLongueur() - 1, y.getLongueur() - 1,
              new Alignement(), y, t);
   }

   public void la(int i, int j, Alignement z, Mot y, Table t) {
      if (i != -1 && j != -1 &&
          t.get(i, j) == t.get(i - 1, j - 1) +
                         this.lettreA(i).sub(y.lettreA(j))) {
         Alignement zz = (Alignement)z.clone();
         zz.ajouterAuDebut(this.lettreA(i), y.lettreA(j));
         la(i - 1, j - 1, zz, y, t);
      }
      if (i != -1 &&
          t.get(i, j) == t.get(i - 1, j) + this.lettreA(i).del()) {
         Alignement zz = (Alignement)z.clone();
         zz.ajouterAuDebut(this.lettreA(i), new Lettre('-'));
         la(i - 1, j, zz, y, t);
      }
      if (j != -1 &&
          t.get(i, j) == t.get(i, j - 1) + y.lettreA(j).ins()) {
         Alignement zz = (Alignement)z.clone();
         zz.ajouterAuDebut(new Lettre('-'), y.lettreA(j));
         la(i, j - 1, zz, y, t);
      }
      if (i == -1 && j == -1)
         System.out.println(z);
   }

   public Automate autoAlignOpt(Mot y, Table t) {
      Automate automate = new Automate();
      int m = this.getLongueur(), n = y.getLongueur();
      TableDEtats e = new TableDEtats(m, n);

      e.set(-1, -1, automate.getInitial());
      e.set(m - 1, n - 1, new Etat());
      e.get(m - 1, n - 1).setTerminal(true);
      this.aa(m - 1, n - 1, y, t, e);
      return automate;
   }

   public void aa(int i, int j, Mot y, Table t, TableDEtats e) {
      if (i != -1 && j != -1 &&
          t.get(i, j) == t.get(i - 1, j - 1) +
                         this.lettreA(i).sub(y.lettreA(j))) {
         if (e.get(i - 1, j - 1) == null) {
            e.set(i - 1, j - 1, new Etat());
            aa(i - 1, j - 1, y, t, e);
         }
         e.get(i - 1, j - 1).setCible(new Couple(this.lettreA(i),
                                      y.lettreA(j)), e.get(i, j));
      }
      if (i != -1 &&
          t.get(i, j) == t.get(i - 1, j) +
                         this.lettreA(i).del()) {
         if (e.get(i - 1, j) == null) {
            e.set(i - 1, j, new Etat());
            aa(i - 1, j, y, t, e);
         }
         e.get(i - 1, j).setCible(new Couple(this.lettreA(i),
                                      new Lettre('-')), e.get(i, j));
      }
      if (j != -1 &&
          t.get(i, j) == t.get(i, j - 1) +
                         y.lettreA(j).ins()) {
         if (e.get(i, j - 1) == null) {
            e.set(i, j - 1, new Etat());
            aa(i, j - 1, y, t, e);
         }
         e.get(i, j - 1).setCible(new Couple(new Lettre('-'),
                                      y.lettreA(j)), e.get(i, j));
      }
   }

   public Table smcSimpleBis(Mot y) {
      int m = this.getLongueur(), n = y.getLongueur();
      Table s = new Table(m, n);

      for (int j = 0; j <= n - 1; ++j)
         for (int i = 0; i <= m - 1; ++i)
            if (this.lettreA(i).equals(y.lettreA(j)))
               s.set(i, j, s.get(i - 1, j - 1) + 1);
            else
               s.set(i, j, Math.max(s.get(i - 1, j), s.get(i, j - 1)));
      return s;
   }

   public int smcSimple(Mot y) {
      Table s = this.smcSimpleBis(y);
      return s.get(this.getLongueur() - 1, y.getLongueur() - 1);
   }

   public Mot unPlusLongSousMotCommun(Mot y, Table s) {
      Mot z = new Mot();
      int m = this.getLongueur(), n = y.getLongueur(), i = m - 1, j = n - 1;

      while (i != -1 && j != -1)
         if (this.lettreA(i).equals(y.lettreA(j))) {
            z.ajouterAuDebut(this.lettreA(i));
            --i;
            --j;
         }
         else if (s.get(i - 1, j) > s.get(i, j - 1))
            --i;
         else
            --j;
      return z;
   }

   public int[] smcColonne(Mot y, int n) {
      int m = this.getLongueur();
      int[] c, c1 = new int[m + 1], c2 = new int[m + 1];

      for (int j = 0; j <= n - 1; ++j) {
         for (int i = 0; i <= m - 1; ++i)
            if (this.lettreA(i).equals(y.lettreA(j)))
               c2[i + 1] = c1[i] + 1;
            else
               c2[i + 1] = Math.max(c1[i + 1], c2[i]);
         c = c1;
         c1 = c2;
         c2 = c;
      }
      return c1;
   }

   public Mot smc(Mot y) {
      Mot aux1, aux2, u, v;
      int k, m = this.getLongueur(), n = y.getLongueur();
      int[] c, c1, c2 = new int[m + 1], p, p1 = new int[m + 1],
            p2 = new int[m + 1];

      if (m == 1 && y.contient(this.lettreA(0)))
         return new Mot(this.lettreA(0));
      else if (n == 1 && this.contient(y.lettreA(0)))
         return new Mot(y.lettreA(0));
      else if (m == 0 || m == 1 || n == 0 || n == 1)
         return new Mot();
      c1 = this.smcColonne(y, n/2);
      for (int i = -1; i <= m - 1; ++i)
         p1[i + 1] = i + 1;
      for (int j = n/2; j <= n - 1; ++j) {
         for (int i = 0; i <= m - 1; ++i)
            if (this.lettreA(i).equals(y.lettreA(j))) {
               c2[i + 1] = c1[i] + 1;
               p2[i + 1] = p1[i];
            }
            else if (c1[i + 1] > c2[i]) {
               c2[i + 1] = c1[i + 1];
               p2[i + 1] = p1[i + 1];
            }
            else {
               c2[i + 1] = c2[i];
               p2[i + 1] = p2[i];
            }
         c = c1;
         c1 = c2;
         c2 = c;
         p = p1;
         p1 = p2;
         p2 = p;
      }
      k = p1[m];
      aux1 = this.getLettres(0, k - 1);
      aux2 = y.getLettres(0, n/2 - 1);
      u = aux1.smc(aux2);
      aux1 = this.getLettres(k, m - 1);
      aux2 = y.getLettres(n/2, n - 1);
      v = aux1.smc(aux2);
      return u.concat(v);
   }

   public int breche(Mot y, int g, int h) {
      int m = this.getLongueur(), n = y.getLongueur(), t;
      Table tt = new Table(m, n), td = new Table(m, n), ti = new Table(m, n);
      int inf = ~0 >>> 1;

      for (int i = -1; i <= m - 1; ++i) {
         td.set(i, -1, inf);
         ti.set(i, -1, inf);
      }
      tt.set(0, -1, g);
      for (int i = 1; i <= m - 1; ++i)
         tt.set(i, -1, tt.get(i - 1, -1) + h);
      tt.set(-1, 0, g);
      for (int j = 1; j <= n - 1; ++j)
         tt.set(-1, j, tt.get(-1, j - 1) + h);
      for (int j = 0; j <= n - 1; ++j) {
         td.set(-1, j, inf);
         ti.set(-1, j, inf);
         for (int i = 0; i <= m - 1; ++i) {
            td.set(i, j, Math.min(td.get(i - 1, j) + h, tt.get(i - 1, j) +g));
            ti.set(i, j, Math.min(ti.get(i, j - 1) + h, tt.get(i, j - 1) +g));
            t = tt.get(i - 1, j - 1) + this.lettreA(i).sub(y.lettreA(j));
            tt.set(i, j, Math.min(t, Math.min(td.get(i, j), ti.get(i, j))));
         }
      }
      return tt.get(m - 1, n - 1);
   }

   public Table alignementLocal(Mot y) {
      int m = this.getLongueur(), n = y.getLongueur();
      Table s = new Table(m, n);

      for (int j = 0; j <= n - 1; ++j)
         for (int i = 0; i <= m - 1; ++i)
            s.set(i, j, Math.max(Math.max(0, s.get(i - 1, j - 1) +
                                             this.lettreA(i).sub(y.lettreA(j))),
                                 Math.max(s.get(i - 1, j) +
                                          this.lettreA(i).del(),
                                          s.get(i, j - 1) +
                                          y.lettreA(j).ins())));
      return s;
   }

   public Vector lDiffDyn(Mot x, int k) {
      int m = x.getLongueur(), n = this.getLongueur();
      Table r = new Table(m, n);
      Vector v = new Vector();

      for (int i = 0; i <= m - 1; ++i)
         r.set(i, -1, i + x.lettreA(i).del());
      for (int j = 0; j <= n - 1; ++j) {
         for (int i = 0; i <= m - 1; ++i)
            r.set(i, j, Math.min(r.get(i - 1, j - 1) + x.lettreA(i).sub(this.lettreA(j)),
                                 Math.min(r.get(i - 1, j) + x.lettreA(i).del(),
                                          r.get(i, j - 1) +
                                          this.lettreA(j).ins())));
         if (r.get(m - 1, j) <= k)
            v.addElement(new Integer(j));
      }
      return v;
   }

   public Vector lDiffElag(Mot x, int k) {
      int m = x.getLongueur(), n = this.getLongueur(), p;
      int[] c, c1 = new int[m], c2 = new int[m];
      Vector v = new Vector();

      for (int i = -1; i <= k - 1; ++i)
         c1[i + 1] = i + 1;
      p = k;
      for (int j = 0; j <= n - 1; ++j) {
         c2[0] = 0;
         for (int i = 0; i <= p; ++i)
            if (x.lettreA(i).equals(this.lettreA(j)))
               c2[i + 1] = c1[i];
            else
               c2[i + 1] = Math.min(c1[i], Math.min(c2[i], c1[i + 1])) + 1;
         c = c1;
         c1 = c2;
         c2 = c;
         while (c1[p + 1] > k)
            --p;
         if (p == m - 1)
            v.addElement(new Integer(j));
         p = Math.min(p + 1, m - 1);
      }
      return v;
   }

   public Vector lDiffDiag(Mot x, int k) {
      int m = x.getLongueur(), n = this.getLongueur(), p;
      Table tl = new Table(k, n - m + k + 2);
      Vector v = new Vector();

      return v;
   }

   public Vector lInegalites(Mot x, int k, File[] fg) {
      File ff = new File(), fj;
      int f = -1, g = -1, m = x.getLongueur(), n = this.getLongueur(), p;
      Vector v = new Vector();

      for (int j = 0; j <= n - m; ++j) {
         if (ff.getLongueur() > 0 && ((Integer)ff.tete()).intValue() == j - f - 1)
            ff.defiler();
         if (j <= g)
            fj = this.inegFusion(f, j, g, ff, fg[j - f], x, k);
         else
            fj = new File();
         if (fj.getLongueur() <= k) {
            ff = fj;
            f = j;
            do {
               ++g;
               if (!x.lettreA(g - j).equals(this.lettreA(g)))
                  ff.enfiler(new Integer(g - j));
            }
            while (ff.getLongueur() <= k && g < j + m - 1);
            if (ff.getLongueur() <= k)
               v.addElement(new Integer(j));
         }
      }
      return v;
   }

   private File inegFusion(int f, int j, int g, File ff, File fg,
                           Mot x, int k) {
      File fj = new File();

      while (fj.getLongueur() <= k && ff.getLongueur() > 0 &&
             fg.getLongueur() > 0) {
         int p = ((Integer)ff.tete()).intValue();
         int q = ((Integer)fg.tete()).intValue();
         if (p < q) {
            ff.defiler();
            fj.enfiler(new Integer(p - j + f));
         }
         else if (q < p) {
            fg.defiler();
            fj.enfiler(new Integer(q - j + f));
         }
         else {
            ff.defiler();
            fg.defiler();
            if (x.lettreA(p - j + f).equals(this.lettreA(f + p)))
               fj.enfiler(new Integer(p - j + f));
         }
      }
      while (fj.getLongueur() <= k && ff.getLongueur() > 0) {
         int p = ((Integer)ff.defilement()).intValue();
         fj.enfiler(new Integer(p - j + f));
      }
      while (fj.getLongueur() <= k && fg.getLongueur() > 0 &&
             ((Integer)fg.tete()).intValue() <= g - f) {
         int q = ((Integer)fg.defilement()).intValue();
         fj.enfiler(new Integer(q - j + f));
      }
      return fj;
   }

   public File[] preLInegalites(int k) {
      int i, m = this.getLongueur();
      File[] fg = new File[m];

      for (int q = 1; q <= m - 1; ++q) {
         fg[q] = new File();
         i = q;
         while (fg[q].getLongueur() < 2*k + 1 && q < i) {
            if (!this.lettreA(i).equals(this.lettreA(i - q)))
               fg[q].enfiler(new Integer(i));
            ++i;
         }
      }
      return fg;
   }

   public Vector lMotifCourt(Mot x, Alphabet alphabet) {
      Lettre a;
      Enumeration e = alphabet.elements();
      int m = x.getLongueur(), masq, n = this.getLongueur(), r;
      int[] s = new int[alphabet.getCard()];
      Vector v = new Vector();

      while (e.hasMoreElements()) {
         a = (Lettre)e.nextElement();
         s[alphabet.rang(a)] = ~0;
      }
      masq = 1;
      for (int i = 0; i <= m - 1; ++i) {
         s[alphabet.rang(this.lettreA(i))] &= masq;
         masq <<= 1;
      }
      masq >>= 1;
      r = ~0;
      for (int j = 0; j <= n - 1; ++j) {
         r = (r << 1) | s[alphabet.rang(this.lettreA(j))];
         if ((r & masq) == 0)
            v.addElement(new Integer(j));
      }
      return v;
   }
         
   public Vector lInegMotifCourt(Mot x, int k, Alphabet alphabet) {
      Lettre a;
      Enumeration e = alphabet.elements();
      int m = x.getLongueur(), masq, n = this.getLongueur(), t, tp;
      int[] r = new int[k + 1], s = new int[alphabet.getCard()];
      Vector v = new Vector();

      while (e.hasMoreElements()) {
         a = (Lettre)e.nextElement();
         s[alphabet.rang(a)] = ~0;
      }
      masq = 1;
      for (int i = 0; i <= m - 1; ++i) {
         s[alphabet.rang(this.lettreA(i))] &= masq;
         masq <<= 1;
      }
      masq >>= 1;
      r[0] = ~0;
      for (int ell = 1; ell <= k; ++ell)
         r[ell] = r[ell - 1] << 1;
      for (int j = 0; j <= n - 1; ++j) {
         t = r[0];
         r[0] = (r[0] << 1) | s[alphabet.rang(this.lettreA(j))];
         for (int ell = 1; ell <= k; ++ell) {
            tp = r[ell];
            r[ell] = ((r[ell] << 1) | s[alphabet.rang(this.lettreA(j))]) &
                   (t << 1);
            t = tp;
         }
         if ((r[k] & masq) == 0)
            v.addElement(new Integer(j));
      }
      return v;
   }

   public Vector lDiffMotifCourt(Mot x, int k, Alphabet alphabet) {
      Lettre a;
      Enumeration e = alphabet.elements();
      int m = x.getLongueur(), masq, n = this.getLongueur(), t, tp;
      int[] r = new int[k + 1], s = new int[alphabet.getCard()];
      Vector v = new Vector();

      while (e.hasMoreElements()) {
         a = (Lettre)e.nextElement();
         s[alphabet.rang(a)] = ~0;
      }
      masq = 1;
      for (int i = 0; i <= m - 1; ++i) {
         s[alphabet.rang(this.lettreA(i))] &= masq;
         masq <<= 1;
      }
      masq >>= 1;
      r[0] = ~0;
      for (int ell = 1; ell <= k; ++ell)
         r[ell] = r[ell - 1] << 1;
      for (int j = 0; j <= n - 1; ++j) {
         t = r[0];
         r[0] = (r[0] << 1) | s[alphabet.rang(this.lettreA(j))];
         for (int ell = 1; ell <= k; ++ell) {
            tp = r[ell];
            r[ell] = ((r[ell] << 1) | s[alphabet.rang(this.lettreA(j))]) &
                   ((t & r[ell - 1]) << 1) & t;
            t = tp;
         }
         if ((r[k] & masq) == 0)
            v.addElement(new Integer(j));
      }
      return v;
   }

}