<div dir="ltr">Hi All,<div><br></div><div>Thank your very much for the answers,<br><div><br></div><div><a class="gmail_plusreply" id="plusReplyChip-0" href="mailto:v@micic.co.za" tabindex="-1">@Valentin Micic</a> , Your lcs function skipping the "World" word. I need "o" and "World" also count. </div><div><br></div><div>@Marc Worrel, Your function also similar with Valentine Micic's function.<br><br>@Richard O'Keefe , I suppose substring or subsequence is same thing, but i think i am wrong, the point is, i need the function to also count </div><div>"o" from <<"Hellaao World">>, and "World" from <<"Hello World">><br>from example: lcs(<<"Hello World">>, <<"Hellaao World">>)</div><div><br></div><div>I think i need to make a NIF . </div><div>I will try to make NIF based on this <a href="https://github.com/wollmers/c-lcs-bv">https://github.com/wollmers/c-lcs-bv</a> wonderful example ANSI C code.</div><div><br></div><div>I've try Pyrlang <a href="https://pyrlang.github.io/Pyrlang/">https://pyrlang.github.io/Pyrlang/</a> in the hope i that i can use / communicate with <a href="https://pypi.org/project/pylcs/">https://pypi.org/project/pylcs/</a> through: </div><div>rpc:call('<a href="mailto:py@127.0.0.1">py@127.0.0.1</a>', 'pylcs', 'lcs', [<<"Hello World">>,<<"Hellaao World">>])  in a python-process node but Pyrlang not help much in my case. still very slow </div><div>because it run over the network.</div><div><br></div><div><br><br></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Pada tanggal Sen, 30 Mar 2020 pukul 20.08 Ben Murphy <<a href="mailto:benmmurphy@gmail.com">benmmurphy@gmail.com</a>> menulis:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi,<br>
<br>
I think the implementation on rosetta code is slightly broken from a<br>
performance point of view. Usually, if you are memoising in this<br>
problem you would use the offsets for where you are in the string. So<br>
if you were writing in an imperative language you would just have a N<br>
x M array. Obviously, you can't do this in Erlang so they are storing<br>
stuff in a dictionary. However, for the keys it looks like they are<br>
using the string/list for the key instead of the offset. This means<br>
the dict code will have to iterate over the remaining bit of the<br>
string for every lookup. So instead of being O(NxM) you end up with an<br>
algorithm that is O(NxMx(N + M)). So instead of being quadratic it<br>
gives you cubic performance. This might explain why it is so slow.<br>
Note: I haven't included the log() term that is introduced by the<br>
dictionary lookup that can't be avoided in Erlang.<br>
<br>
On Mon, Mar 30, 2020 at 11:18 AM I Gusti Ngurah Oka Prinarjaya<br>
<<a href="mailto:okaprinarjaya@gmail.com" target="_blank">okaprinarjaya@gmail.com</a>> wrote:<br>
><br>
> Hi,<br>
><br>
> I need longest common substring erlang implementation. Please help me<br>
><br>
> I've tried <a href="https://rosettacode.org/wiki/Longest_common_subsequence#Erlang" rel="noreferrer" target="_blank">https://rosettacode.org/wiki/Longest_common_subsequence#Erlang</a> but very very slow T_T<br>
><br>
> and i've tried binary:longest_common_prefix([<<"i love you 2020-03-28">>,<<"i love you 2020-03-01">>]) not effective / not valid<br>
><br>
> Thank you<br>
><br>
</blockquote></div>