Created
December 24, 2015 22:20
-
-
Save vishesh/9037d77a28b36df4eeeb to your computer and use it in GitHub Desktop.
Longest palindrome subsequence
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (* hacker rank longest palindrome subsequence *) | |
| open Core.Std | |
| open Option | |
| let lcs_palin_naive str = | |
| let rec find i j = | |
| match (i, j) with | |
| | (x, y) when x = y -> 1 | |
| | (x, y) when y < x -> 0 | |
| | _ -> | |
| if str.[i] = str.[j] then | |
| 2 + (find (i + 1) (j - 1)) | |
| else | |
| max (find (i + 1) j) (find i (j - 1)) | |
| in | |
| find 0 (String.length str - 1);; | |
| let lcs_palin str = | |
| let len = String.length str in | |
| let table = Array.make_matrix ~dimx:len ~dimy:len 0 in | |
| for i = 0 to len - 1 do | |
| table.(i).(i) <- 1 | |
| done; | |
| for l = 2 to len do | |
| for i = 0 to len - l do | |
| let j = i + l - 1 in | |
| if str.[i] = str.[j] && l = 2 then | |
| table.(i).(j) <- 2 | |
| else if str.[i] = str.[j] then | |
| table.(i).(j) <- table.(i + 1).(j - 1) + 2 | |
| else | |
| table.(i).(j) <- max table.(i).(j - 1) table.(i + 1).(j) | |
| done | |
| done; | |
| table.(0) | |
| (* | |
| let palin_split str = | |
| let len = String.length str in | |
| let cutpoints = List.range 1 len in | |
| List.map cutpoints ~f:(fun cp -> | |
| (lcs_palin (String.sub str ~pos:0 ~len:cp)) * | |
| (lcs_palin (String.sub str ~pos:cp ~len:(len - cp)))) | |
| |> List.max_elt ~cmp:(-) | |
| |> Option.value ~default:0;; | |
| *) | |
| let lcs_palin_split str = | |
| let t1 = lcs_palin str in | |
| let t2 = lcs_palin (String.rev str) in | |
| let len = String.length str in | |
| let rec loop i result = | |
| if i = len then | |
| result | |
| else | |
| loop (i + 1) (max result (t1.(i) * t2.(len - i - 1))) | |
| in | |
| loop 0 0 | |
| let test () = | |
| lcs_palin_naive "BBABCBCAB" |> printf "%d = 7\n"; | |
| lcs_palin_naive "GEEKS FOR GEEKS" |> printf "%d = 7\n"; | |
| lcs_palin_split "BBABCBCAB" |> printf "%d = 7\n"; | |
| lcs_palin_split "GEEKS FOR GEEKS" |> printf "%d = 7\n"; | |
| lcs_palin_split "eeegeeksforskeeggeeks" |> printf "%d = 50\n" | |
| ;; | |
| let main () = | |
| read_line () |> lcs_palin_split |> printf "%d\n";; | |
| test ();; | |
| (*main ();;*) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment