(*   ESIM 2000   *)
                         

            (* I - Parcours en escalier dans un tableau *)
          

 let remplir n =
   let m= make_matrix (n+1) (n+1) 1 in   
                      (* m.(0).(0) initialise' _ 1 *)
  
   (* premie`re colonne *)
   for i=1 to n do m.(i).(0) <- 2 * m.(i-1).(0) done; 
 
   (* colonnes suivantes *)
   for j=1 to n do
         for i=0 to n do m.(i).(j) <- 3 * m.(i).(j-1) 
         done 
   done;
   m;;
  
 let pgcd m i j k l =
   let p = min i k and q = min j l in m.(p).(q);;
   
 let pgm m p =
       let n =(vect_length m) -1 in
       let i = ref(0) and j = ref(n) and j0 = ref(n) in
       while m.(0).(!j0)> p do j0 := !j0 - 1 done;
       j := !j0;                  (* ligne d'indice 0 *)

       for i0=1 to n do           (* lignes suivantes *)
          if !j0 >= 0  && m.(i0).(!j0) > p  
          then  j0 := !j0 -1 
          else if !j0 >= 0 &&  m.(!i).(!j) < m.(i0).(!j0) then
              begin i := i0; j := !j0 end   
       done;
       (!i, !j,  m.(!i).(!j)) ;;  
   
     

            (* II - Codage de mots en partie commune *)
         

  type arbre = 
               | nil
               | noeud of char * arbre * arbre ;;
               
  let dico = ref(noeud(`.`,nil,nil)) ;;
  
  let creer_branche m = 
     let n = string_length m in
     let rec aux i =
           if i = n then noeud(`.`,nil,nil)
           else noeud(m.[i],aux (i+1),nil)
     in aux 0 ;;      
               
  let etete m = sub_string  m 1 (string_length m - 1) ;;

 
  let rec placer m a = 
     if m="" then a 
     else match a with
           |         nil  -> creer_branche m
           | noeud(c,g,d) -> if c = m.[0]  
                             then noeud(c,placer (etete m) g, d)
                             else noeud(c, g, placer m d) ;;
                             
     
  let rec inserer m a = 
     if m="" then a 
     else match a with
         |         nil  -> creer_branche m
         | noeud(c,g,d) -> if c = m.[0]  
                           then noeud(c,inserer(etete m) g, d)
                           else if c < m.[0]
                                then noeud(c, g, inserer m d)
                                else noeud(m.[0], creer_branche(etete m), a);;
               (* on tient compte cette fois de l'ordre alphabe'tique *)
                             
  


 let affiche a =    
      let rec parcours  aa accu = match aa with 
           |          nil -> ()
           | noeud(c,g,d) -> if c=`.`            

              (* accu contient le mot lu sur le chemin allant
                de la racine au noeud actuellement visit‚ *)

                    then begin 
                             print_string accu; 
                             print_newline(); parcours d accu 
                           end
                      else begin
                             parcours g (accu^(string_of_char c));    
                             parcours d accu
                           end
      in parcours a "";;                            
  
 

   let present m a =    
      let rec parcours  aa accu = match aa with 
           |          nil -> false
           | noeud(c,g,d) -> if c=`.` 
           
               then m=accu || parcours d accu                           
               else parcours g (accu^(string_of_char c)) || parcours d accu
      in parcours a "";;                            
  
  

  let saisir () = 
     let mot = ref ("") in
        while !mot <> "fin" do 
            mot := read_line();
            if !mot <> "fin" then dico := inserer !mot !dico 
        done ;;
                        

    
            (* III - Expressions pr_fix_es bien form_es *)
            

  let est_bien_forme u =
    let n = u.(0) and i = ref (1) and s = ref (0)  in
    while (!s >=0) && (!i <= n) do
      s := !s + u.(!i);
      i := !i + 1;
    done;
    (!i > n) && (!s = -1) ;;
  
  let construire u v =
    let m =  u.(0) and n = v.(0) in
    let w = make_vect (m+n+2) 1 in
      w.(0) <- m+n+1;
      for i = 1 to m do w.(i+1)   <- u.(i) done;
      for j = 1 to n do w.(j+m+1) <- v.(j) done;
      w;;
    
  let fusion l1 l2 = 
    let rec aux  u ll = match ll with 
       |   []  -> []
       | v::q  -> (construire u v)::(aux u q) in
    let rec parcours liste = match liste with
       |   []  -> []
       | u::q  -> (aux u l2)@(parcours q) in
    parcours l1;; 
      
  let enumere p = 
    let t = make_vect (p+1) [] in
    t.(0) <- [[|1;-1|]];
    for k=1 to p do
      for i=0 to k-1 do t.(k) <- t.(k)@fusion (t.(i)) (t.(k-1-i))
      done
    done;
    t;;  
    

  (***************************  FIN  ********************************)