type etat={
  id: int;
  conditions_darrive: (char list) option;
  mutable voisins: (etat list) option;
  terminal:bool;
}

let new_state n cond v t = {id=n; conditions_darrive=cond; voisins=v; terminal=t}

let make_automate regexp =
  let id = ref 0 in
    
  let ajoute_voisin  etat new_voisin =
    match etat.voisins with
 None -> etat.voisins<- Some [ new_voisin ]
      | Some v -> etat.voisins<- Some (new_voisin::v)
  in
  let rec make_state regexp_conditions term successeur=
    match regexp_conditions with
 Epsilon -> id:=!id+1; 
   new_state !id None successeur term
      | Char c -> id:=!id+1;
   new_state !id (Some [c]) successeur term
      | Orchar clist -> id:=!id+1; 
   new_state !id (Some  clist) successeur term
      | Plus r -> id:=!id+1;
   let plus= new_state !id None successeur term in
   let premier = make_state r false (Some [plus]) in
   let loop = make_state r false (Some [plus]) in
     ajoute_voisin  plus loop;
     premier
      | Star r -> id:=!id+1;
   let star= new_state !id None successeur term in
   let loop = make_state r false (Some [star]) in
     ajoute_voisin  star loop;
     star
      | Or (r1,r2) ->let s1 = make_state r1 term successeur in
 let s2 = make_state r2 term successeur in
   id:=!id+1;
   new_state !id None (Some [s1; s2]) false
      | Groupe r -> make_state r term successeur
   (*id:=!id+1;
   let g= new_state !id None successeur term in
     ajoute_voisin g ( make_state r false (Some [g]) );
     g *)
      | List (r1,r2) -> let s2 = make_state r2 term None in
   make_state r1 false ( Some [s2] )
  in
    new_state 0 None (Some [make_state regexp true None]) false


let print_automate automate =
  let already_print = ref [] in
    
  let print_condition id c=
    Printf.printf "\t%c -> etat %d\n" c id
  in
  let print_conditions_option etat =
    match etat.conditions_darrive with
 None -> Printf.printf "\t goto etat %d\n" etat.id
      | Some cdts -> List.iter (print_condition etat.id) cdts
  in
  let rec print_etat etat =
    if List.exists ( (=) etat.id) !already_print then ()
    else
      (already_print:= etat.id::!already_print;
       Printf.printf "Etat %d" etat.id;
       if etat.terminal then
  Printf.printf " (Terminal)\n%!"
       else
  Printf.printf "\n%!"
       ;
       match etat.voisins with
    None ->Printf.printf "Pas de voisins\n%!"
  | Some vss ->
      List.iter print_conditions_option vss;
      List.iter print_etat vss)
  in
    print_etat automate;
    flush_all ()


exception Reconnu
  
let reconnaitre automate str=
  
  let rec test_and_go etat str i cdt =
    if ( Char.compare str.[i] cdt )=0 then
  reconrec etat str (i+1)
  
  and goto_etat str i etat=
    match etat.conditions_darrive with
 None -> reconrec etat str i
      | Some cdts ->
   if i>= String.length str then
     ()
   else
     List.iter (test_and_go etat str i) cdts
  
  and reconrec etat str i=
    if String.length str = i && etat.terminal then
      raise Reconnu
    else
      match etat.voisins with
   None -> ()
 | Some vss -> List.iter (goto_etat str i) vss     
  in
    try 
      reconrec automate str 0;
      false
    with
 Reconnu -> true