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

Question

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

1
121
12234
20345
21345

现在，如果我搜索 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";

输出

121

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

输出

121

---

更新

或者，该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);

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