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

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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://608388]
help
Chatterbox?
[atcroft]: .oO(Then there is the effect if a site changes their timezone, such as when the International Date Line was moved by the purchase of Alaska by the US from Russia in 1867, or several places (I cannot recall off-hand) that moved from one side of the Date
[atcroft]: Line to the other recently....)
[atcroft]: .oO(Then again, you also have to be careful if you had it to the database, and be aware of any assumptions it makes (such as SQLite assuming Gregorian calendar and a day of exactly 86400 seconds)...)

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (4)
As of 2017-04-29 04:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I'm a fool:











    Results (531 votes). Check out past polls.