Anonymous user
Longest common subsequence: Difference between revisions
added ocaml
m (→Recursion: Grammar) |
(added ocaml) |
||
Line 240:
return sb.reverse().toString();
}</java>
=={{header|OCaml}}==
===Recursion===
from Haskell
<ocaml>let longest xs ys = if List.length xs > List.length ys then xs else ys
let rec lcs a b = match a, b with
[], _
| _, [] -> []
| x::xs, y::ys ->
if x = y then
x :: lcs xs ys
else
longest (lcs a ys) (lcs xs b)</ocaml>
===Dynamic programming===
<ocaml>let lcs xs' ys' =
let xs = Array.of_list xs'
and ys = Array.of_list ys' in
let n = Array.length xs
and m = Array.length ys in
let a = Array.make_matrix (n+1) (m+1) [] in
for i = n-1 downto 0 do
for j = m-1 downto 0 do
a.(i).(j) <- if xs.(i) = ys.(j) then
xs.(i) :: a.(i+1).(j+1)
else
longest a.(i).(j+1) a.(i+1).(j)
done
done;
a.(0).(0)</ocaml>
Because both solutions only work with lists, here are some functions to convert to and from strings:
<ocaml>let list_of_string str =
let result = ref [] in
String.iter (fun x -> result := x :: !result)
str;
List.rev !result
let string_of_list lst =
let result = String.create (List.length lst) in
ignore (List.fold_left (fun i x -> result.[i] <- x; i+1) 0 lst);
result</ocaml>
Both solutions work. Example:
<pre>
# string_of_list (lcs (list_of_string "thisisatest") (list_of_string "testing123testing"));;
- : string = "tsitest"
</pre>
=={{header|Python}}==
| |||