module type Traitement= sig val traitement : string -> string -> (string -> string -> int) -> (string*string*string)list end;; module Traitement_S_W= struct let remplir_matrice m query comp q c sub= let gap=sub "-" "a" in m.(0).(0)<-0; for j = 1 to c do m.(0).(j)<-m.(0).(j-1)+gap; done; for i=1 to q do m.(i).(0)<-m.(i-1).(0)+gap; for j=1 to c do let m1= m.(i-1).(j-1) + (sub (String.sub query (i-1) 1) (String.sub comp (j-1) 1)) in let m2= m.(i-1).(j)+ gap in let m3= m.(i).(j-1)+ gap in let mm= min m2 m3 in m.(i).(j)<-min m1 mm; done; done; ;; let corr a b= if (compare a b = 0) then "|" else if (compare a "-" = 0) then " " else if (compare b "-" = 0) then " " else ":" ;; let rec tout_alignement m query lg_q comp lg_c s1 s2 s3 sub rep= if (lg_q!=0) then let q=String.sub query (lg_q-1) 1 in if (lg_c!= 0) then begin let c=String.sub comp (lg_c-1) 1 in if (m.(lg_q).(lg_c)==m.(lg_q-1).(lg_c-1)+sub q c ) then tout_alignement m query (lg_q - 1) comp (lg_c - 1) (q^s1) ((corr q c)^s2) (c^s3) sub rep; if (m.(lg_q).(lg_c)==m.(lg_q-1).(lg_c)+sub q "-") then tout_alignement m query (lg_q - 1) comp (lg_c) (q^s1) ((corr q "-")^s2) (" "^s3) sub rep; if (m.(lg_q).(lg_c)==m.(lg_q).(lg_c-1)+sub "-" c ) then tout_alignement m query (lg_q) comp (lg_c - 1) (" "^s1) ((corr "-" c)^s2) (c^s3) sub rep; end else tout_alignement m query (lg_q - 1) comp (lg_c ) (q^s1) ((corr q "-")^s2) (" "^s3) sub rep else if (lg_c!= 0) then let c=String.sub comp (lg_c-1) 1 in tout_alignement m query (lg_q) comp (lg_c - 1) (" "^s1) ((corr "-" c)^s2) (c^s3) sub rep else begin rep:=(s1,s2,s3)::!rep; ();end ;; let traitement query comp sub= let lg_q=String.length query in let lg_c=String.length comp in let mat =Array.create_matrix (lg_q+1) (lg_c+1) 0 in let sol1= "" in let sol2= "" in let sol3= "" in remplir_matrice mat query comp lg_q lg_c sub; let rep=ref [] in tout_alignement mat query lg_q comp lg_c sol1 sol2 sol3 sub rep; !rep ;; end;; module Plus_longue_chaine_commune_sans_gap= struct let subloc a b =if compare a b = 0 then 1 else if compare a " " = 0 then -1 else if compare b " " = 0 then -1 else -3 ;; let remplir_matrice m query comp lg_q lg_c = m.(0).(0)<-0; for j=1 to lg_c do m.(0).(j)<-0; done; for i=1 to lg_q do m.(i).(0)<-0; for j=1 to lg_c do let q=String.sub query (i-1) 1 in let c=String.sub comp (j-1) 1 in m.(i).(j)<-max (m.(i-1).(j-1)+subloc q c) (max (m.(i-1).(j)+subloc q " ") (m.(i).(j-1)+subloc " " c )) done; done; ;; let rech_sol mat lg_q lg_c pos= let vale=ref 0 in for i=1 to lg_q do for j=1 to lg_c do if mat.(i).(j)>(!vale) then vale:=mat.(i).(j); pos=(i,j); done; done; ;; let trace_back i j m query comp lg_q lg_c = let s1="" in let s2="" in let s3="" in for a=(lg_c-1) downto j+1 do s1=s1^" "; s2=s2^" "; s3=s3^String.sub comp (a-1) 1; done; if j!=0 then begin let q=String.sub query (i-1) 1 in let c=String.sub comp (j-1) 1 in s1=q^s1; s2="|"^s2; s3=c^s3; while (m.(i).(j)==m.(i).(j-1)+subloc q c ) do i=i-1; j=j-1; let q=String.sub query (i-1) 1 in let c=String.sub comp (j-1) 1 in s1=q^s1; s2="|"^s2; s3=c^s3; done; end; for a=j downto 0 do s1=" "^s1; s2=" "^s2; s3=(String.sub comp (a-1) 1)^s3; done; [(s1,s2,s3)]; ;; let traitement query comp sub= let lg_q=String.length query in let lg_c=String.length comp in let mat =Array.create_matrix (lg_q+1) (lg_c+1) 0 in remplir_matrice mat query comp lg_q lg_c; let i=0 in let j=0 in rech_sol mat lg_q lg_c (i,j); trace_back i j mat query comp lg_q lg_c ;; end;;