longest_common_subsequence.sf

#!/usr/bin/ruby

#
## https://rosettacode.org/wiki/Longest_common_subsequence#Sidef
#

#
## This is generalized version which works with strings
## but also with arrays of any kind, such as arrays of characters.
#

func lcs(xstr, ystr) is cached {

    xstr.is_empty && return xstr;
    ystr.is_empty && return ystr;

    var(x, xs, y, ys) = (xstr.slice(0,1), xstr.slice(1),
                         ystr.slice(0,1), ystr.slice(1));

    if (x == y) {
        x + lcs($xs, $ys)
    } else {
        [lcs(xstr, ys), lcs(xs, ystr)].max_by { .len };
    }
}

say lcs("thisisatest", "testing123testing")
say lcs(%g"thisisatest", %g"testing123testing")

assert_eq(lcs("thisisatest", "testing123testing"), "tsitest")
assert_eq(lcs(%g"thisisatest", %g"testing123testing"), "tsitest".chars)