let reconnaissance f t =
  let n = string_length f and compteur = ref 0 and état = ref 0
  in  
  let P = make_vect (n + 1) "" and PA = make_vect (2 * n + 2) ""
  and AlphaPA = make_vect (2 * n + 2) 0 and AlphaP = make_vect n 0
  and T = make_matrix (n + 1) 2 0
  in
  for k = 0 to n do P.(k) <- sub_string f 0 k done;
  for k = 0 to n do PA.(2 * k) <- P.(k)^"a"; PA.(2 * k + 1) <- P.(k)^"b" done;
  for k = 1 to n
  do
    let p = P.(k)
    in
    let i = if PA.(2 * k - 2) = p then AlphaPA.(2 * k - 2) else AlphaPA.(2 * k - 1)
    in
    if P.(i + 1) = P.(i)^"a" then
      (AlphaPA.(2 * k) <- i + 1; AlphaPA.(2 * k + 1) <- AlphaPA.(2 * i + 1))
    else
      (AlphaPA.(2 * k) <- AlphaPA.(2 * i); AlphaPA.(2 * k + 1) <- i + 1)
  done;
  for k = 0 to 2 * n - 1 do if PA.(k) = P.(k / 2 + 1) then AlphaP.(k / 2) <- AlphaPA.(k) done;
  if n <> 0 & P.(1) = "a" then T.(0).(0) <- 1;
  if n <> 0 & P.(1) = "b" then T.(0).(1) <- 1;
  for k = 1 to n - 1
  do
    T.(k).(0) <- if P.(k)^"a" = P.(k + 1) then k + 1 else T.(AlphaP.(k - 1)).(0);
    T.(k).(1) <- if P.(k)^"b" = P.(k + 1) then k + 1 else T.(AlphaP.(k - 1)).(1)
  done;
  if n <> 0 then T.(n).(0) <- T.(AlphaP.(n - 1)).(0);
  if n <> 0 then T.(n).(1) <- T.(AlphaP.(n - 1)).(1);
  for k = 0 to string_length t - 1
  do
    let j = if t.[k] = `a` then 0 else 1
    in
    état := T.(!état).(j);
    if !état = n then incr compteur
  done;
  !compteur;;
  
reconnaissance "aba" "abaabbaaababa";;

------------------------------------------------------------------------------------------------

let tableMax = 128;;

type macro_definition = {Symbole : string ; Definition : string};;

let EntreeVide = {Symbole = "" ; Definition = ""};;

type 'a table_des_symboles = {Table : 'a vect ; mutable TailleTable : int};;
  
let TableDesSymboles = {Table = make_vect tableMax EntreeVide ; TailleTable = 0};;

TableDesSymboles.Table.(3) <- {Symbole = "Info" ; Definition = "Informatique"};
TableDesSymboles.Table.(4) <- {Symbole = "Permute" ; Definition = "$2$1"};
TableDesSymboles.Table.(2) <- {Symbole = "Echange" ; Definition = "$2,$1"};
TableDesSymboles.Table.(0) <- {Symbole = "Cat" ; Definition = "$1$2"};
TableDesSymboles.Table.(1) <- {Symbole = "Commentaire" ; Definition = ""};
TableDesSymboles.Table.(5) <- {Symbole = "x" ; Definition = "xx()"};
TableDesSymboles.Table.(6) <- {Symbole = "xx" ; Definition = "xxx()"};
TableDesSymboles.Table.(7) <- {Symbole = "y" ; Definition = "y()"};
TableDesSymboles.TailleTable <- 8;;

let estDansTable chaine =
  try
    for k = 0 to TableDesSymboles.TailleTable - 1
    do if TableDesSymboles.Table.(k).Symbole = chaine then raise Exit done;
    false
  with Exit -> true;;
      
estDansTable "Cat";;

let defDansTable chaine =
  let def = ref ""
  in
  try
    for k = 0 to TableDesSymboles.TailleTable - 1
    do
      if TableDesSymboles.Table.(k).Symbole = chaine then
      begin def := TableDesSymboles.Table.(k).Definition; raise Exit end
    done;
    invalid_arg (chaine^" n'est pas un symbole actif")
  with Exit -> !def;;
  
defDansTable "x";;

defDansTable "coucou";;

let avant = prefix <=;;

let defDansTableNouveau chaine =
  let g = ref 0 and d = ref (TableDesSymboles.TailleTable - 1) and def = ref ""
  in
  try
    while !g <= !d
    do
      let m = (!g + !d) / 2
      in
      if TableDesSymboles.Table.(m).Symbole = chaine then
        begin def := TableDesSymboles.Table.(m).Definition; raise Exit end
      else
        if avant TableDesSymboles.Table.(m).Symbole chaine then g := m + 1 else d := m - 1
    done;
    invalid_arg (chaine^" n'est pas un symbole actif")
  with Exit -> !def;;
  
defDansTableNouveau "xx";;

deDansTableNouveau "exemple fumeux";;

let estDansTableNouveau chaine =    
  let g = ref 0 and d = ref (TableDesSymboles.TailleTable - 1)
  in
  try
    while !g <= !d
    do
      let m = (!g + !d) / 2
      in
      if TableDesSymboles.Table.(m).Symbole = chaine then raise Exit
      else if avant TableDesSymboles.Table.(m).Symbole chaine then g := m + 1 else d := m - 1
    done;
    false
  with Exit -> true;;