# spoj-ocaml / 00033.TRIP / trip.ml

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109``` ```(* http://www.spoj.pl/problems/TRIP/ *) let (|>) x y = y x let id x = x let str_reverse s = let n = String.length s in let s' = String.make n ' ' in for i = 0 to n - 1 do s'.[i] <- s.[n - i - 1] done ; s' module CharOrderedType = struct type t = Char.t let compare = compare end module CharMap = Map.Make(CharOrderedType) type prefix_tree = Empty | Node of prefix_tree CharMap.t let rec merge_trees a b = match a, b with Empty, _ -> b | _, Empty -> a | Node a', Node b' -> Node (CharMap.fold (fun char subtree tree -> CharMap.add char (if CharMap.mem char tree then merge_trees subtree (CharMap.find char tree) else subtree) tree) a' b') (* F[i][j] = F[i-1][j-1] + 1 if a[i] == b[j] F[i][j] = max(F[i-1][j], F[i][j-1]) otherwise *) let f_calc a b n m = let f = Array.make_matrix (n + 1) (m + 1) 0 in for i = 1 to n do for j = 1 to m do if a.[i - 1] == b.[j - 1] then f.(i).(j) <- f.(i - 1).(j - 1) + 1 else f.(i).(j) <- max f.(i - 1).(j) f.(i).(j - 1) done done ; f let gen_tree f a b n m = let cache = Array.make_matrix (n + 1) (m + 1) Empty in for i = 1 to n do for j = 1 to m do cache.(i).(j) <- if a.[i - 1] == b.[j - 1] then (* Node (CharMap.singleton a.[i - 1] cache.(i - 1).(j - 1) *) Node (CharMap.add a.[i - 1] cache.(i - 1).(j - 1) CharMap.empty) else merge_trees (if f.(i).(j) == f.(i - 1).(j) then cache.(i - 1).(j) else Empty) (if f.(i).(j) == f.(i).(j - 1) then cache.(i).(j - 1) else Empty) done done ; cache.(n).(m) let print_solutions f n m tree = let str = String.make f.(n).(m) ' ' in let rec ps_aux i = function Empty -> print_endline str | Node m -> CharMap.iter (fun key subtree -> str.[i] <- key ; ps_aux (i + 1) subtree) m in ps_aux 0 tree let solve a b = let n = String.length a and m = String.length b and a = str_reverse a and b = str_reverse b in let f = f_calc a b n m in gen_tree f a b n m |> print_solutions f n m let main () = Gc.set { (Gc.get ()) with Gc.minor_heap_size=16777216 } ; let t = Scanf.scanf "%d\n" id in for i = 1 to t do let a = Scanf.scanf "%s\n" id and b = Scanf.scanf "%s\n" id in solve a b ; print_newline () done let () = main () ```