PFIサマーインターン2011問題の解法の一例

http://research.preferred.jp/2011/07/intern2011_problem/
を分割統治法で解く。

let find_freq x =
  let open String in
  let rec aux x len remain =
    Printf.printf "%s, %d, %c\n" (sub x 0 len) len remain;
    match len with
    | 1 -> get x 0
    | 0 -> remain
    | _ ->
	let rec pair i len_next =
	  if i = len / 2 then (* problem size halved *)
	    (len_next, if len land 1 = 1 then get x (len - 1) else remain)
	  else match get x (2 * i) with
	    c when c = get x (2 * i + 1) ->
	      set x len_next c; (* constant time operation *)
	      pair (i + 1) (len_next + 1)
	  | _ ->
	      pair (i + 1) len_next
	in
	let (len_next, remain_next) = pair 0 0 in
	aux x len_next remain_next
  in
  aux (copy x) (length x) ' '

let x1 = "aabbababa"
let x2 = "aabbaabbaabbaabbccddaaabbabaababaaaaabaa"
let x3 = "baabbaa"
let x4 = "abcaabaca"
let x5 = "abcaabaac"
let xs = [x1; x2; x3; x4; x5];;

List.iter (fun x -> Printf.printf "ans : %c\n\n" (find_freq x)) xs