(* The Z Algorithm *) (* From: Algorithms on Strings, Trees and Sequences *) (* by Dan Gusfield, Cambridge University Press, 1997 *) (* $Id: zalgorithm.ml,v 1.1 2003/01/12 15:33:00 berke Exp $ *) (* Implementation by Berke Durak on 30042001 *) let compute_z m z s = (* Correctness preconditions : *) (* l,r,k,z given *) (* Condition I : *) (* Forall k' Forall i *) (* 0 < k' < k && *) (* 0 <= i < z.(k') => s.[0 + i] = s.[k' + i] *) (* Postcondition : *) (* Forall k *) (* z.(k) = check 0 k 0 *) (* Condition II : *) (* Forall i *) (* l <= i <= r => s.[i - l] = s[i] *) let rec loop l r k = if k < m then begin if r < k then (* we know nothing. must compute *) let n = check 0 k 0 in (* z_k = n *) (* l = k *) (* r = k + n - 1 *) z.(k) <- n; loop k (k + n - 1) (k + 1) else (* we know something : *) (* s.[l .. l + z.(l) - 1] = s.[0 ... z.(l) - 1] *) (* s.[l .. r] = s.[0 .. r - l + 1] *) (* therefore z.(k) >= z.(k - l) *) (* further z.(k) <= r - k + 1 *) (* thus z.(k) >= min z.(k - l) (r - k + 1 *) let z' = min z.(k - l) (r - k + 1) in let n = check z' (k + z') z' in z.(k) <- n; let r' = k + n - 1 in if r > r' then loop l r (k + 1) else loop k r' (k + 1) end and check i j n = if i < m && j < m && s.[i] = s.[j] then check (i + 1) (j + 1) (n + 1) else n in z.(0) <- m; if m > 1 then begin z.(1) <- check 0 1 0; loop 1 z.(1) 2 end let alphabet = "abcdefghijklmnopqrstuvwxyz" let _ = Random.self_init (); let a = Sys.argv.(1) in (* alphabet *) let m = int_of_string (Sys.argv.(2)) in let n = String.length a in let s = String.make m a.[0] and z = Array.make m 0 and h = Array.make (m + 1) 0 in for i = 0 to int_of_string (Sys.argv.(3)) do for j = 0 to m - 1 do s.[j] <- a.[Random.int n]; done; compute_z m z s; (* Printf.printf "%s :" s; *) z.(0) <- 0; let l = Array.fold_left max 0 z in h.(l) <- h.(l) + 1 done; for i = 1 to m - 1 do Printf.printf "%d %d\n" i h.(i) done