Perl：进行最长前缀匹配的最佳方法（字符串）

Question

我有一个大约 5000 个单词的列表。我想在给定单词的这些单词中找到最长的前缀匹配。例如，在我的列表中我有：

现在如果我搜索 12134，结果将是 121（最长匹配）。我知道可以用不同的方式来完成。但是，最有效的方法应该是什么？

Answer 1

#!/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";

产出

Answer 2

您可以让正则表达式引擎为您执行此操作。应该很快

我希望很明显，正则表达式模式只需构建一次，然后可用于为任意数量的目标字符串查找最长前缀

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  if $target =~ /^($re)/;

输出

更新

或者，Tree::Trie 模块可用于实现正则表达式引擎提供的 trie 搜索，如下所示

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

输出当然和前面的代码一样

Perl：进行最长前缀匹配的最佳方法（字符串）

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

perl

longest-prefix

输出

更新