Получение самой длинной общей подпоследовательности в ERLANG

Question

Я новичок в этом ERLANG, я знаю основы. Это похоже на схему, но более широкую. Я знаю, как создать функцию, но у меня возникают проблемы с созданием функции, которая получает самую длинную общую подпоследовательность.

lcs(str1,str2) это функция, которая будет принимать два строки и вывод целого число:

lcs(algorithm,logarithm) выведет на экране 7, потому что самая длинная общая подпоследовательность, которые могут быть сделаны в lgrithm, который по размеру 7.

Любой ответ очень приветствуется.

Answer 1

У вас есть очень хорошая реализация алгоритма ЛВП доступна на Rosettacode, который:

-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 

-

Edit: Сделано алгоритм немного легче понять

Кэш здесь представляет собой интересный способ улучшить производительность алгоритма в некоторых случаях, но здесь этого не требуется. Мы можем просто написать, удаление кэша:

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. ЛВП из «» и все равно 0.
2. То же самое для ЛСК чего-либо и «».
3. LCS двух слов, начинающихся по одной и той же букве, это LCS двух слов минус первая буква плюс 1.
4. LCS двух слов, начинающихся с разных букв, является максимальным значением (a) LCS первое слово минус первая буква и второе, и (б) LCS первого слова, а второе минус первая буква.