56 lines
1.5 KiB
Lua
56 lines
1.5 KiB
Lua
--- Longest Common Subsequence algorithm.
|
|
-- After pseudo-code in <a
|
|
-- href="http://www.ics.uci.edu/~eppstein/161/960229.html">lecture
|
|
-- notes</a> by <a href="mailto:eppstein@ics.uci.edu">David Eppstein</a>.
|
|
module ("lcs", package.seeall)
|
|
|
|
|
|
-- Find common subsequences.
|
|
-- @param a first sequence
|
|
-- @param b second sequence
|
|
-- @return list of common subsequences
|
|
-- @return the length of a
|
|
-- @return the length of b
|
|
local function commonSubseqs (a, b)
|
|
local l, m, n = {}, #a, #b
|
|
for i = m + 1, 1, -1 do
|
|
l[i] = {}
|
|
for j = n + 1, 1, -1 do
|
|
if i > m or j > n then
|
|
l[i][j] = 0
|
|
elseif a[i] == b[j] then
|
|
l[i][j] = 1 + l[i + 1][j + 1]
|
|
else
|
|
l[i][j] = math.max (l[i + 1][j], l[i][j + 1])
|
|
end
|
|
end
|
|
end
|
|
return l, m, n
|
|
end
|
|
|
|
--- Find the longest common subsequence of two sequences.
|
|
-- The sequence objects must have an <code>__append</code> metamethod.
|
|
-- This is provided by <code>string_ext</code> for strings, and by
|
|
-- <code>list</code> for lists.
|
|
-- @param a first sequence
|
|
-- @param b second sequence
|
|
-- @param s an empty sequence of the same type, to hold the result
|
|
-- @return the LCS of a and b
|
|
function longestCommonSubseq (a, b, s)
|
|
local l, m, n = commonSubseqs (a, b)
|
|
local i, j = 1, 1
|
|
local f = getmetatable (s).__append
|
|
while i <= m and j <= n do
|
|
if a[i] == b[j] then
|
|
s = f (s, a[i])
|
|
i = i + 1
|
|
j = j + 1
|
|
elseif l[i + 1][j] >= l[i][j + 1] then
|
|
i = i + 1
|
|
else
|
|
j = j + 1
|
|
end
|
|
end
|
|
return s
|
|
end
|