/* Recherches dans des tableaux de booleens    */

public class RecherchesDansTableauBooleen {

/////////////////////////////////////////////////  

/* Generation d'un tableau de booleens         */
/* tires au sort                               */

  static boolean [] generationAleatoire(int n) {
    int i;
    boolean [] t = new boolean[n];
    for ( i = 0 ; i < n ; i++ ) {
      t[i] = ( Math.random() < 0.5); }
    return t;
  }

/* Affichage d'un tableau de booleens          */
/*  - '0' pour faux                            */
/*  - '1' pour vrai                            */

  static void afficher(boolean [] t) {
    int i;
    for ( i = 0 ; i < t.length ; i++ ) {
      if ( t[i] ) {
        Ecran.afficher('1'); }
        else {
        Ecran.afficher('0'); } }
  }

/* Calcul du nombre de booleens vrai           */
/* presents dans un tableau de booleens        */

  static int nombreDeVrais(boolean [] t) {
    int i;
    int nb;
    nb = 0;
    for ( i = 0 ; i < t.length ; i++ ) {
      if ( t[i] ) {
        nb = nb+1; } }
    return nb;
  }

/* Calcul du nombre de series de booleens      */
/* identiques consecutifs presentes            */
/* dans un tableau de booleens                 */

  static int nombreSeries(boolean [] t) {
    int i;
    int nb;
    boolean enCours;
    enCours = t[0];
    nb = 1;
    for ( i = 1 ; i < t.length ; i++ ) {
      if ( t[i] != enCours ) {
        nb = nb+1;
        enCours = t[i]; } }
    return nb;
  }

/* Calcul de la longueur maximale de toutes    */
/* les series de vrais consecutifs presents    */
/* dans un tableau de booleens                 */
  
  static int longueurMaxSeriesVrais(boolean [] t) {
    int i;
    int lMax;
    int cpt;
    boolean enCours;
    lMax = 0;
    cpt = 0;
    enCours = false;
    for ( i = 0 ; i < t.length ; i++ ) {
      if ( t[i] ) {
        if ( !enCours ) {
          cpt = 0;
          enCours = true; }
        cpt = cpt+1; }
        else {
        if ( enCours ) {
          if ( cpt > lMax ) {
            lMax = cpt; }
          enCours = false; } } }
    if ( enCours ) {
      if ( cpt > lMax ) {
        lMax = cpt; } }
    return lMax;
  }

/* Test si un motif de booleens coincide       */
/* avec les booleens presentes dans un tableau */
/* de booleens a partir d'un indice            */  
  
  static boolean concordance(boolean [] motif,boolean [] t,int p) {
    int i;
    boolean res;
    i = 0;
    res = true;
    while ( ( res ) && ( i < motif.length ) ) {
      res = ( motif[i] == t[p] );
      i = i+1;
      p = p+1; }
    return res;
  }
  
/* Determination de l'indice de la premiere    */
/* occurrence d'un motif de booleens           */
/* recherche dans un tableau de booleens       */
/* Retourne -1 si motif non present            */
  
  static int premiereOccurrence(boolean [] motif,boolean [] t) {
    int pos;
    int i;
    int nt;
    pos = -1;
    i = 0;
    nt = t.length-motif.length+1;
    while ( ( pos == -1 ) && ( i < nt ) ) {
      if ( concordance(motif,t,i) ) {
        pos = i; }
      i = i+1; }
    return pos;
  }

/* Retourne un tableau de booleens construit   */
/* a partir d'une chaine de caracteres         */
/* ou les 0 codent des faux et les 1 codent    */
/* des vrais                                   */
  
  static boolean [] motif(String s) {
    int i;
    char [] tc;
    boolean [] t = new boolean[s.length()];
    tc = s.toCharArray();
    for ( i = 0 ; i < t.length ; i++ ) {
      switch (tc[i]) {
        case '0' :
          t[i] = false;
          break;
        case '1' :
          t[i] = true;
          break;
        default :
          Ecran.afficherln("Erreur!!!");
          break; } }
    return t;
  }

/////////////////////////////////////////////////

/* Programme principal                         */

  public static void main(String [] args) {
    boolean [] t;
    int n;
    int nb;
    int lm;
    boolean [] motif;
    int pos;
    String s;
    Ecran.afficher("Taille du tableau ? ");
    n = Clavier.saisirInt();
    t = generationAleatoire(n);
    afficher(t);
    Ecran.sautDeLigne();
    nb = nombreDeVrais(t);
    Ecran.afficherln("Nombre de vrai                 : ",nb);
    nb = nombreSeries(t);
    Ecran.afficherln("Nombre de series               : ",nb);
    nb = longueurMaxSeriesVrais(t);
    Ecran.afficherln("Longueur max des series de vrai: ",nb);
    Ecran.afficher("Longueur du motif ? ");
    lm = Clavier.saisirInt();
    motif = generationAleatoire(lm);
    afficher(motif);
    Ecran.sautDeLigne();
    pos = premiereOccurrence(motif,t);
    Ecran.afficherln("Position du motif              : ",pos);
    Ecran.afficher("Motif ? ");
    s = Clavier.saisirString();
    motif = motif(s);
    pos = premiereOccurrence(motif,t);
    Ecran.afficherln("Position du motif              : ",pos);
  }
}