Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Re: Challenge: Fast Common Substrings

by eric256 (Parson)
on Apr 05, 2007 at 00:03 UTC ( #608388=note: print w/ replies, xml ) Need Help??

in reply to Challenge: Fast Common Substrings

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));

Eric Hodges

Comment on Re: Challenge: Fast Common Substrings
Download Code

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://608388]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (11)
As of 2015-11-25 15:49 GMT
Find Nodes?
    Voting Booth?

    What would be the most significant thing to happen if a rope (or wire) tied the Earth and the Moon together?

    Results (681 votes), past polls