23 lines
769 B
Plaintext
23 lines
769 B
Plaintext
defmodule LCS do
|
|
def longest_common_substring(a,b) do
|
|
alist = to_charlist(a) |> Enum.with_index
|
|
blist = to_charlist(b) |> Enum.with_index
|
|
lengths = for i <- 0..length(alist)-1, j <- 0..length(blist), into: %{}, do: {{i,j},0}
|
|
Enum.reduce(alist, {lengths,0,""}, fn {x,i},acc ->
|
|
Enum.reduce(blist, acc, fn {y,j},{map,gleng,lcs} ->
|
|
if x==y do
|
|
len = if i==0 or j==0, do: 1, else: map[{i-1,j-1}]+1
|
|
map = %{map | {i,j} => len}
|
|
if len > gleng, do: {map, len, String.slice(a, i - len + 1, len)},
|
|
else: {map, gleng, lcs}
|
|
else
|
|
{map, gleng, lcs}
|
|
end
|
|
end)
|
|
end)
|
|
|> elem(2)
|
|
end
|
|
end
|
|
|
|
IO.puts LCS.longest_common_substring("thisisatest", "testing123testing")
|