Correction

• Sujet

• Retour à la page des TP

(* Question 1 *)

(* Les lettres d'un facteur (== sous-chaîne) de w doivent être consécutives dans w. *)
(* Les lettres d'une sous-séquence (== sous-mot) de w n'ont pas à l'être (« à lettre », huhu). *)

(* Question 2 *)

let khrass_mp c t =
	let m = string_length c and n = string_length t in
	let rec aux l i =
		if i = n - m + 1 then
			rev l
		else
			aux (if sub_string t i m = c then i::l else l) (i + 1)
	in aux [] 0
;;

khrass_mp "aba" "aabaaaba";;

(* Complexité : O(mn) *)

(* Question 3 *)

(* w a au plus |w| bords (où |·| est la longueur d'un mot) *)
(* On peut définir une relation d'ordre total sur les bords : a < b ssi a est bord de b *)
(* Une fois qu'ils sont totalement ordonnés b_1 > ? > b_n, on a : bêta(b_i) = b_{i + 1} pour tout i *)

(* Question 4 *)

let kmp s =
	let n = string_length s in
	let l = make_vect (n + 1) 0 in
	for i = 1 to n - 1 do
		let k = ref i in
		while s.[i] <> s.[l.(!k)] & !k > 0 do
			k := l.(!k)
		done;
		(* Quand on sort de la boucle, soit s.[i] = s.[l.(!k)], soit !k = 0 *)
		l.(i + 1) <- if s.[i] = s.[l.(!k)] then l.(!k) + 1 else 0
	done;
	l
;;

kmp "abababbaba";; (* 0 0 0 1 2 3 4 0 1 2 3 *)
kmp "abaabab";; (* 0 0 0 1 1 2 3 2 *)

(* Question 5 *)

let trouver_occurrences u v =
	let t = kmp (u ^ "#" ^ v) in
	let n = string_length u in
	let m = string_length v in
	let c = ref 0 in
	let rec cherche occurrences i =
		if i == 1 + n + m + 1 then 
			rev occurrences
		else
			cherche (if t.(i) = n then (i - 2 * n - 1)::occurrences else occurrences) (i + 1)
	in cherche [] (2 * n + 1);
;;

trouver_occurrences "aba" "aabaaaba";;

(* Question 6 *)

let facteur_carre s =
	let n = string_length s in
	let a_facteur_carre = ref false in
	for i = 0 to n - 1 do
		let t = kmp (sub_string s i (n - i)) in
		for j = 1 to n - i do
			if j mod 2 == 0 && t.(j) = j / 2 then
				a_facteur_carre := true
		done
	done;
	!a_facteur_carre
;;

facteur_carre "ab";;
facteur_carre "abab";;

(* Question 7 *)

let est_primitif s =
	let n = string_length s in
	let t = kmp s in
	t.(n) > 0 && n mod (n - t.(n)) = 0
;;

est_primitif "ab";;
est_primitif "aaa";;
est_primitif "abab";;

(* Question 8 *)

let miroir s =
	let t = ref "" in
	let n = string_length s in
	for i = n - 1 downto 0 do
		t := !t ^ string_of_char s.[i]
	done;
	!t
;;

let prefixes_palindromes s =
	let n = string_length s in
	let t = kmp (s ^ "#" ^ miroir s) in
	let rec aux l i =
		if i = 1 then
			l
		else
			aux (sub_string s 0 t.(i)::l) t.(i)
	in aux [] (2 * n + 1)
;;

prefixes_palindromes "aabaab";;

(* Question 9 *)

let conjugues u v =
	let w = v ^ v in
	let n = string_length u in
	let l = trouver_occurrences u w in
	if l = [] then false else
	let i = hd l in
	v = sub_string w 0 i ^ sub_string w (i + n) (n - i)
;;

conjugues "abab" "bbaa";;
conjugues "abab" "baba";;