40 lines
1.3 KiB
Erlang
40 lines
1.3 KiB
Erlang
-module(lcs).
|
|
|
|
%% API exports
|
|
-export([
|
|
lcs/2
|
|
]).
|
|
|
|
%%====================================================================
|
|
%% API functions
|
|
%%====================================================================
|
|
|
|
lcs(A, B) ->
|
|
{LCS, _Cache} = get_lcs(A, B, [], #{}),
|
|
lists:reverse(LCS).
|
|
|
|
%%====================================================================
|
|
%% Internal functions
|
|
%%=====================================================
|
|
|
|
get_lcs(A, B, Acc, Cache) ->
|
|
case maps:find({A, B, Acc}, Cache) of
|
|
{ok, LCS} -> {LCS, Cache};
|
|
error ->
|
|
{NewLCS, NewCache} = compute_lcs(A, B, Acc, Cache),
|
|
{NewLCS, NewCache#{ {A, B, Acc} => NewLCS }}
|
|
end.
|
|
|
|
compute_lcs(A, B, Acc, Cache) when length(A) == 0 orelse length(B) == 0 ->
|
|
{Acc, Cache};
|
|
compute_lcs([Token |ATail], [Token |BTail], Acc, Cache) ->
|
|
get_lcs(ATail, BTail, [Token |Acc], Cache);
|
|
compute_lcs([_AToken |ATail]=A, [_BToken |BTail]=B, Acc, Cache) ->
|
|
{LCSA, CacheA} = get_lcs(A, BTail, Acc, Cache),
|
|
{LCSB, CacheB} = get_lcs(ATail, B, Acc, CacheA),
|
|
LCS = case length(LCSA) > length(LCSB) of
|
|
true -> LCSA;
|
|
false -> LCSB
|
|
end,
|
|
{LCS, CacheB}.
|