Shortest common supersequence: Difference between revisions
→{{header|Phix}}
Thundergnat (talk | contribs) m (→{{header|Ring}}: Remove vanity tags) |
|||
Line 261:
Longest common subsequence: bcba
Shortest common supersquence: abdcabdab
</pre>
=={{header|Phix}}==
{{trans|Python}}
<lang Phix>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")</lang>
{{out}}
<pre>
"abdcabdab"
"WEASRDANCELS"
</pre>
| |||