/usr/share/ettercap/lua/third-party/lcs.lua is in ettercap-common 1:0.8.2-10build4.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | --- 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>.
-- 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
local 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
-- Public interface
local M = {
longestCommonSubseq = longestCommonSubseq,
}
return M
|