1. Vadim Shender
  2. spoj-ocaml

Source

spoj-ocaml / 00033.TRIP / trip.ml

(* 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 ()