P is for Practical | |
PerlMonks |
Re: Challenge: Fast Common Substringsby blokhead (Monsignor) |
on Apr 04, 2007 at 02:04 UTC ( [id://608180]=note: print w/replies, xml ) | Need Help?? |
Here's just a naive solution using regexes. I have no idea if it's fast. On one hand, the regex engine is doing all the work; on the other hand, in the second code snippet, it's just brute-forcing the problem. The match_all_ways sub is taken from Re^3: Delimited Backtracking with Regex.
Returns all the common substrings, since it might as well.. In scalar context returns the number. Update: Or, if you want the regex engine to do all of the work, instead of computing the intersection of the two lists in perl: Note that the match_all_ways sub was changed slightly (to account for the different capturing). Disclaimer: If input strings contain a newline or null character, or if $len > 65536, it doesn't work.. but I think you get the idea. These solutions are both trivial to extend to a range of lengths.. just pass "n,m" as the $len argument. blokhead
In Section
Seekers of Perl Wisdom
|
|