(**************************************************************************) (* *) (* Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre, *) (* Kim Nguyen, Laurent Sartre *) (* *) (* Informatique - MP2I/MPI - CPGE 1re et 2e années. *) (* Cours et exercices corrigés. Éditions Ellipses, 2022. *) (* *) (* https://www.informatique-mpi.fr/ *) (* *) (**************************************************************************) (* recherche d'un motif dans un texte avec l'algorithme de Boyer--Moore *) let build_table m = let lm = String.length m in let table = Array.make_matrix lm 256 (-1) in for j = 0 to lm - 1 do for k = 0 to j - 1 do table.(j).(Char.code m.[k]) <- k done done; table let boyer_moore m t = let lm = String.length m and lt = String.length t in let table = build_table m in let count = ref 0 in let i = ref 0 in while !i <= lt - lm do let rec compare j = if j < 0 then ( Printf.printf "occurrence à la position %d\n" !i; incr count; 1 ) else if t.[!i + j] <> m.[j] then j - table.(j).(Char.code t.[!i + j]) else compare (j - 1) in i := !i + compare (lm - 1) done; !count