37 lines
1.6 KiB
Plaintext
37 lines
1.6 KiB
Plaintext
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
|