Re: searching problem (reverse substrings)

[LanX]

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