use v6;

# code adapted from
# http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring#Perl
# instead of the full matrix of suffixes we only use two rows, one for the
# previous suffix length, one for current.

sub LCS($s1, $s2) {
    my $lcs_len = 0;
    my ($l1, $l2) = ($s1, $s2)>>.chars;
    my @char1 = Str, $s1.comb;
    my @char2 = Str, $s2.comb;
    my @previous_suffix = 0 xx ($l2 + 1);
    my $lcs = '';
    for 1..$l2 -> $n1 {
        my @current_suffix = 0 xx ($l2 + 1);
        for 1..$l2 -> $n2 {
            next unless @char1[$n1] eq @char2[$n2];

            # look, current common substring just got one longer!
            # RAKUDO #80614: I would have liked to write that as
            # my $c = @current_suffix[$n] = ...
            # but a bug in rakudo prevents that :(
            @current_suffix[$n2] = my $c = @previous_suffix[$n2 - 1] + 1;


            if $c > $lcs_len {
                # ... and it's the best we've got!
                $lcs_len = $c;
                $lcs = $s1.substr($n1 - $c, $c);
            }
        }
        # avoid copying by using binding
        @previous_suffix := @current_suffix;
    }
    return $lcs;
}

multi MAIN {
    say LCS get, get;
}

multi MAIN('test') {
    use Test;
    plan *;
    is LCS('otherworldlinesses', 'physiotherapy'), 'other', 'masaks example 1';
    is LCS('physiotherapy', 'otherworldlinesses'), 'other', 'masaks example 2';

    done_testing;
}