Re: Challenge: Fast Common Substrings

[eric256]

I dunno about speed, but its the only version i can actualy understand so far ;) and who knows, it might not be as slow as you think...probably will be..but hey! I think the second loop through s2 could probably have some short circuits added where it knows the sub string it is on doesn't occur in the first string..but it's time to go home!

use strict;
use warnings;

use Data::Dumper;

sub common_sub {
    my ($s1,$s2,$len) = @_;

    my $len_s1 = length($s1);
    my $len_s2 = length($s2);

    my $match_s1 = {};
    my $match_s2 = {};
    
    for my $start (0..length($s1)-1) {
        for my $l (1..$len) {
            next if $start+$l > $len_s1;
            $match_s1->{substr($s1, $start, $l)} ||= 1;
        }
    }

    for my $start (0..length($s2)-1) {
        for my $l (1..$len) {
            next if $start+$l > $len_s2;
            $match_s2->{substr($s2, $start, $l)} ||= 1;
        }
    }
    $match_s1->{$_}++ for keys %$match_s2;
    return grep { $match_s1->{$_} == 2 } keys %$match_s1;
}

print join(",", common_sub("ABCD", "BCD",2));