string - 获取ERLANG中最长的公共(public)子序列

Question

我是这个 ERLANG 的新手，我了解基础知识。这就像计划，但范围更广。我知道如何创建一个函数，但我在创建一个获取最长公共(public)子序列的函数时遇到了问题。

lcs(str1,str2) 是一个接受两个字符串并输出一个整数的函数:

lcs(algorithm,logarithm) 会输出7，因为最长的公共(public)子序列是lgrithm，即7 大小。

非常感谢任何回答。

Answer 1

您可以在 Rosettacode 上很好地实现 LCS 算法，即:

-module(lcs).
-compile(export_all).

lcs_length(S,T) ->
    {L,_C} = lcs_length(S,T,dict:new()),
    L.

lcs_length([]=S,T,Cache) ->
    {0,dict:store({S,T},0,Cache)};
lcs_length(S,[]=T,Cache) ->
    {0,dict:store({S,T},0,Cache)};
lcs_length([H|ST]=S,[H|TT]=T,Cache) ->
    {L,C} = lcs_length(ST,TT,Cache),
    {L+1,dict:store({S,T},L+1,C)};
lcs_length([_SH|ST]=S,[_TH|TT]=T,Cache) ->
    case dict:is_key({S,T},Cache) of
        true -> {dict:fetch({S,T},Cache),Cache};
        false ->
            {L1,C1} = lcs_length(S,TT,Cache),
            {L2,C2} = lcs_length(ST,T,C1),
            L = lists:max([L1,L2]),
            {L,dict:store({S,T},L,C2)}
    end.

lcs(S,T) ->
    {_,C} = lcs_length(S,T,dict:new()),
    lcs(S,T,C,[]).

lcs([],_,_,Acc) ->
    lists:reverse(Acc);
lcs(_,[],_,Acc) ->
    lists:reverse(Acc);
lcs([H|ST],[H|TT],Cache,Acc) ->
    lcs(ST,TT,Cache,[H|Acc]);
lcs([_SH|ST]=S,[_TH|TT]=T,Cache,Acc) ->
    case dict:fetch({S,TT},Cache) > dict:fetch({ST,T},Cache) of
        true ->
            lcs(S,TT,Cache, Acc);
        false ->
            lcs(ST,T,Cache,Acc)
    end.

用作:

raringbeast:Code pierre $ erl
Erlang R15B01 (erts-5.9.1) [source] [64-bit] [smp:8:8] [async-threads:0] [hipe]
[kernel-poll:false]

Eshell V5.9.1  (abort with ^G)
1> c(lcs).
{ok,lcs}
2> lcs:lcs("logarithm", "algorithm").
"lgrithm"
3> lcs:lcs_length("logarithm", "algorithm").
7

--

编辑:使算法更容易理解

这里的缓存只是在某些情况下提高算法性能的一种有趣的方式，但这里不是必需的。我们可以只写，删除缓存:

lcs_length([],_T) ->
    0;
lcs_length(_S,[]) ->
    0;
lcs_length([_H|ST],[_H|TT]) ->
    1 + lcs_length(ST,TT);
lcs_length([_SH|ST]=S,[_TH|TT]=T) ->
    L1 = lcs_length(S,TT),
    L2 = lcs_length(ST,T),
    lists:max([L1,L2]). 

总结:

1. “”和任何东西的 LCS 都是 0。
2. 对于任何东西和“”的 LCS 都是一样的。
3. 以相同字母开头的两个单词的 LCS 是两个单词的 LCS 减去第一个字母加 1。
4. 以不同字母开头的两个单词的 LCS 是 (a) 第一个单词的 LCS 减去第一个字母和第二个字母，以及 (b) 第一个单词和第二个单词的 LCS 减去第一个字母的最大值.