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