/* Recherches dans des tableaux de booleens      */

public class RecherchesDansTableauBooleen {

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

/* Generation et retour d'un tableau de booleens */
/* tires au sort avec equiprobabilite            */
/* n : La taille du tableau à générer            */

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

/* Affichage complet d'un tableau de booleens    */
/*  - '0' pour false                             */
/*  - '1' pour true                              */
/* t : Le tableau de booleens à afficher         */

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

/* Calcul et retour du nombre de booleens true   */
/* presents dans un tableau de booleens          */
/* t : Le tableau de booleens                    */

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

/* Calcul et retour du nombre de series          */
/* de booleens identiques consecutifs presentes  */
/* dans un tableau de booleens                   */
/* t : Le tableau de booleens                    */

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

/* Calcul et retour de la longueur maximale      */
/* de toutes les series de true consecutifs      */
/* presents dans un tableau de booleens          */
/* t : Le tableau de booleens                    */
  
  static int longueurMaxSeriesVrais(boolean [] t) {
    int lMax;
    int cpt;
    boolean enCours;
    lMax = 0;
    cpt = 0;
    enCours = false;
    for ( int i = 0 ; i < t.length ; i++ ) {
      if ( t[i] ) {
        if ( !enCours ) {
          cpt = 0;
          enCours = true; }
        cpt++; }
        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              */  
/* motif : Le tableau de booleens motif          */
/* t : Le tableau de booleens où est effectué    */
/*     le test                                   */
/* p : L'indice de recherche                     */
  
  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++;
      p++; }
    return res;
  }
  
/* Determination et retour de l'indice           */
/* de la 1ère occurrence d'un motif de booleens  */
/* recherché dans un tableau de booleens         */
/* Retour de -1 si motif non present             */
/* motif : Le tableau de booleens motif          */
/* t : Le tableau de booleens où est effectuée   */
/*     la recherche                              */
  
  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; }
        else {
        i++; } }
    return pos;
  }

/* Calcul et retour un tableau de booleens       */
/* construit à partir d'une chaine de caracteres */
/* ou les 0 codent des false et les 1 codent     */
/* des true                                      */
/* s : La chaine de caractères                   */
  
  static boolean [] motif(String s) {
    boolean [] t = new boolean[s.length()];
    char [] tc = s.toCharArray();
    for ( int 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) {
    int n;
    int nb;
    int lm;
    boolean [] motif;
    int pos;
    String s;
    Ecran.afficher("Taille du tableau ? ");
    n = Clavier.saisirInt();
    boolean [] 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);
  }
}