Longest common subsequence: Difference between revisions
Content deleted Content added
m WP link |
+Icon+Unicon |
||
Line 405:
<lang haskell>*Main> lcs "thisisatest" "testing123testing"
"tsitest"</lang>
== Icon and Unicon ==
==={{header|Icon}}===
This solution is a modified variant of the recursive solution. The modifications include (a) deleting all characters not common to both strings and (b) stripping off common prefixes and suffixes in a single step.
IPL reference for strings for deletec
<lang Icon>procedure main()
LCSTEST("thisisatest","testing123testing")
LCSTEST("","x")
LCSTEST("x","x")
LCSTEST("beginning-middle-ending","beginning-diddle-dum-ending")
end
link strings
procedure LCSTEST(a,b) #: helper to show inputs and results
write("lcs( ",image(a),", ",image(b)," ) = ",image(res := lcs(a,b)))
return res
end
procedure lcs(a,b) #: return longest common sub-sequence of characters (modified recursive method)
local i,x,y
local c,nc
if *(a|b) = 0 then return "" # done if either string is empty
if a == b then return a # done if equal
if *(a ++ b -- (c := a ** b)) > 0 then { # find all characters not in common
a := deletec(a,nc := ~c) # .. remove
b := deletec(b,nc) # .. remove
} # only unequal strings and shared characters beyond
i := 0 ; while a[i+1] == b[i+1] do i +:=1 # find common prefix ...
if *(x := a[1+:i]) > 0 then # if any
return x || lcs(a[i+1:0],b[i+1:0]) # ... remove and process remainder
i := 0 ; while a[-(i+1)] == b[-(i+1)] do i +:=1 # find common suffix ...
if *(y := a[0-:i]) > 0 then # if any
return lcs(a[1:-i],b[1:-i]) || y # ... remove and process remainder
return if *(x := lcs(a,b[1:-1])) > *(y := lcs(a[1:-1],b)) then x else y # divide, discard, and keep longest
end</lang>
Sample output:<pre>lcs( "thisisatest", "testing123testing" ) = "tsitest"
lcs( "", "x" ) = ""
lcs( "x", "x" ) = "x"
lcs( "beginning-middle-ending", "beginning-diddle-dum-ending" ) = "beginning-iddle-ending"</pre>
==={{header|Unicon}}===
The Icon solution works in Unicon.
=={{header|J}}==
| |||