type mot =
    {
      lettres : string ;
      debut : int ;
      fin : int
    }

let mot s = 
  {
    lettres = s ;
    debut = 0 ;
    fin = string_length s
  }

let couper m i =
  if i < m.debut || i > m.fin then
    failwith "Mauvais decoupage!"
  else
    { lettres = m.lettres ; debut = m.debut ; fin = i } , 
    { lettres = m.lettres ; fin = m.fin ;debut = i }

(* ----------------------------------------------------------------- *)

type regex == mot -> bool

let facteur f m =
  m.fin - m.debut = string_length f 
    && sub_string m.lettres m.debut (m.fin - m.debut) = f

let facteur = (facteur : string -> regex)

let vide m = 
  m.fin = m.debut

let vide = (vide : regex)

let a = lettre `a`
let bc = facteur "bc"
let non = a (mot "b")
let oui = a (mot "a")
let non = bc (mot "abc")
let oui = bc (mot "bc")

(* ----------------------------------------------------------------- *)

let ou a b m = 
  a m || b m

let ou = (ou : regex -> regex -> regex)

let oui = (ou a bc) (mot "bc")

(* ----------------------------------------------------------------- *)

let puis a b m =
  let essai = ref m.debut in 
  while
    !essai <= m.fin && 
    let debut,fin = couper m !essai in
    not (a debut && b fin)
  do
    incr essai
  done;
  !essai < m.fin

let puis = (puis : regex -> regex -> regex)

let oui = (puis a bc) (mot "abc")

(* ----------------------------------------------------------------- *)

let rec etoile a m = 
  vide m || 
  begin 
    let essai = ref (m.debut + 1) in
    while 
      !essai <= m.fin &&
      let debut,fin = couper m !essai in
      not (a debut && etoile a fin)
    do
      incr essai
    done;
    !essai < m.fin
  end

let etoile = (etoile : regex -> regex)
      
(* ----------------------------------------------------------------- *)

(* (a|ba)*(b|e) *)

(* L = { a^n b^n } 

   Soit R une ER qui reconnait L.
   
   Puisque L est infini, R contient une sous-expression T* et il 
   existe un mot w de L tel que w = utu' et t, non vide, est reconnu 
   par T*. 

   Donc T reconnait au moins un mot non vide x, et donc R, qui reconnait
   utu', reconnait également utxxu', qui est donc dans L.

   Donc x contient autant de a que de b (pour respecter la proportion). 

   Donc xx contient un b (premier x) avant un a (deuxième x), ce qui 
   n'est pas possible si utxxu' est dans L.

   Donc R n'existe pas.
*)

(* ----------------------------------------------------------------- *)

let tout m = true

let tout = (tout : regex)

let contient m n = 
  puis tout (puis (facteur m) tout) (mot n)

let oui = contient "car" "decarcasser"
let non = contient "car" "flibustier"

let recherche m n =
  let pos = ref (0,0) in
  let lire t = 
    if facteur m t 
    then ( pos := t.debut,t.fin ; true )
    else false
  in
  if puis tout (puis lire tout) (mot n)
  then !pos
  else raise Not_found

let oui = recherche "car" "decarcasser"
let non = recherche "car" "flibustier"