(phixonline)-->
with javascript_semantics
function longest_common_subsequence(sequence a, b)
sequence res = ""
if length(a) and length(b) then
if a[$]=b[$] then
res = longest_common_subsequence(a[1..-2],b[1..-2])&a[$]
else
sequence l = longest_common_subsequence(a,b[1..-2]),
r = longest_common_subsequence(a[1..-2],b)
res = iff(length(l)>length(r)?l:r)
end if
end if
return res
end function
function shortest_common_supersequence(string a, b)
string lcs = longest_common_subsequence(a, b),
scs = ""
-- Consume lcs
while length(lcs) do
integer c = lcs[1]
if a[1]==c and b[1]==c then
-- Part of the lcs, so consume from all strings
scs &= c
lcs = lcs[2..$]
a = a[2..$]
b = b[2..$]
elsif a[1]==c then
scs &= b[1]
b = b[2..$]
else
scs &= a[1]
a = a[2..$]
end if
end while
-- append remaining characters
return scs & a & b
end function
?shortest_common_supersequence("abcbdab", "bdcaba")
?shortest_common_supersequence("WEASELS", "WARDANCE")