Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Re: searching problem (reverse substrings)

by LanX (Canon)
on Jan 18, 2013 at 10:33 UTC ( #1014030=note: print w/ replies, xml ) Need Help??


in reply to searching problem

You mean matching only from the start?

Your sorting technique sounds clever, but the sorting itself isn't constant, I suppose something like O(n*log(n)).

IMHO the fastest solution should be a trie, if it's worth the overhead depends on the number of words to search.

Another simpler approach is abusing the regex engine, because from 5.10 on it has internal trie optimization and is f*ckingly fast!

$str = join "\0",@wordlist, @reverts = map { "\0" . reverse $_ } @wordlist; $pattern = '(' . join('|',@reverts) . ')' ; @matches = ( $str =~ /$pattern/g );

thats untested pseudo-code I hope you get the idea! =)

UPDATE

now tested:

DB<131> @wordlist=qw(mamy dady bara foo bic ymamaa arabic ); => ("mamy", "dady", "bara", "foo", "bic", "ymamaa", "arabic") DB<132> $str = join "\0",@wordlist, => "mamy\0dady\0bara\0foo\0bic\0ymamaa\0arabic" DB<133> $pattern = join '|',map { "\0" . reverse $_ } @wordlist; => "\0ymam|\0ydad|\0arab|\0oof|\0cib|\0aamamy|\0cibara" DB<134> @matches = ( $str =~ /($pattern)/g ); => ("\0ymam", "\0arab")

Cheers Rolf


Comment on Re: searching problem (reverse substrings)
Select or Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (13)
As of 2014-12-17 21:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (34 votes), past polls