📘 Finding the longest common substring using Perl 6

📘 Finding the longest common substring using Raku

N. B. Perl 6 has been renamed to Raku. Click to read more.


Find the longest common substring in the given two strings.

Let us limit ourselves with finding only the first longest substring. If there are more common substrings of the same length, then the rest are ignored. There are two loops (see also Task 17, The longest palindrome) over the first string ($a), and they use the indexmethod to search for the substring in the second string ($b).

my $a = 'the quick brown fox jumps over the lazy dog';
my $b = 'what does the fox say?';

my $common = '';
for 0 .. $a.chars -> $start {
    for $start .. $a.chars - 1 -> $end {
        my $s = $a.substr($start, $a.chars - $end);
        if $s.chars > $common.chars && $b.index($s).defined {
           $common = $s;
        }
    }
}

say $common 
    ?? "The longest common substring is '$common'." 
    !! 'There are no common substrings.';

The index method returns the position of the substring $s if it is found in the string $b. It is a little bit tricky to check if the substring is found because when it is found at the beginning of the string, then the returned value is 0 (as 0 is the position of the substring). If the substring is not found, then Nil is returned. Nil is not a numeric value; thus, it cannot be compared using the == or != operators. Use the defined method to check if index returns a value, not Nil$b.index($s).defined.

3 thoughts on “📘 Finding the longest common substring using Perl 6”

  1. Can’t decide if I like this version better or worse than yours:

    my $a = 'the quick brown fox jumps over the lazy dog';
        my $b = 'what does the fox say?';
    
        sub length-sorted-substrs($a) {
            gather for $a.chars, *-1 ... 1 -> $l {
                for 0 .. $a.chars - $l -> $n {
                    take $a.substr($n, $l);
                }
            }
        }
    
        for length-sorted-substrs($a) -> $aa {
            if $b ~~ / "$aa" / {
                say "Longest common substring is *$aa*";
                exit;
            }
        }
    
        say "There are no common substrings.";

Leave a Reply to Anonymous Cancel reply