Perl: best way to do longest prefix match (string)

Question

I have a list of around 5000 words. I want to find the longest prefix match among those words for a given word. For example, in my list I have :

Now If I search for 12134 the result will be 121 (longest match). I know it can be done in different ways. But, what should be the most efficient way ?

If you only have 5000 words in your list, I wouldn't worry too much about efficiency. Any reasonable approach will find the match in a tiny fraction of a second. You can find a list of options [here](http://www.perlmonks.org/?node_id=305753). — Mark Reed, Aug 03 '15 at 02:12

score 3 · Accepted Answer · answered Aug 03 '15 at 02:27

3

#!/usr/bin/env perl

use strict;
use warnings;

my @prefixes = qw(
    1
    121
    12234
    20345
    21345
);

my $num = '12134';

my ($longest) = sort { length $b <=> length $a } grep { 0 == index $num, $_ } @prefixes;

print "$longest\n";

Outputs

answered Aug 03 '15 at 02:27

Miller

34,962
4
39
60

isnt the <=> operator used for sorting numbers? in my case I may also have chars in my list like 1#55 etc. – Kamrul Khan Aug 03 '15 at 07:09
1

That's because it's comparing the length of the match, not the match itself. – ChatterOne Aug 03 '15 at 07:30

Borodin · Answer 2 · 2015-08-03T04:44:57.950

You can get the regex engine to do this for you. It should be very fast

I hope it's obvious that the regex pattern needs to be built only once, and can then be used to find the longest prefix for any number of target strings

use strict;
use warnings;
use 5.010;

my @prefixes = qw/
    1
    121
    12234
    20345
    21345
/;

my $target = 12134;

my $re = join '|', sort { length $b <=> length $a } @prefixes;
$re = qr/(?:$re)/;

say $1 if $target =~ /^($re)/;

output

Update

Alternatively, the Tree::Trie module can be used to implement the trie search that the regex engine provides like this

use strict;
use warnings;
use 5.010;

use Tree::Trie;

my @prefixes = qw/
    1
    121
    12234
    20345
    21345
/;

my $target = 12134;

my $trie = Tree::Trie->new({ deepsearch => 'prefix' });
$trie->add(@prefixes);

say scalar $trie->lookup($target);

The output, of course, is the same as that of the previous code

This may slow down [somewhere around 6,553 prefixes](http://stackoverflow.com/q/29217346/176646) but should be fine for the OP's ~5,000. — ThisSuitIsBlackNot, Aug 03 '15 at 02:45

Perl: best way to do longest prefix match (string)

2 Answers2

output

Update