检查给定字符串是否有效匹配一组前缀

Question

使用什么算法来检查给定字符串是否与一组前缀匹配，以及该组中的哪个前缀？

其他变体：给定路径和一组目录，如何检查路径是否在一组目录中（假设没有符号链接，或者它们不重要）？

我对算法的描述或名称感兴趣，或者解决这个问题的 Perl 模块（或者可以用来解决这个问题）。

编辑
允许有效查找字符串集（目录集）之间的关系的解决方案的奖励积分

例如，给定的目录集：foo、foo/bar、foo/ baz, quux, baz/quux, baz/quux/plugh 该算法是找到 foo 是 foo/bar 和 foo/ 的前缀baz，并且 baz/quux 是 baz/quux/plugh 的前缀...希望没有 O(n^2) 时间。

Answer 1

执行此操作的有效方法是使用 Trie：

http://en.wikipedia.org/wiki/Trie

CPAN 上有一个包：

https://metacpan.org/pod/Tree ::Trie

（虽然我自己从未使用过该包）

您需要考虑哪些操作需要最有效。在 Trie 中进行查找非常便宜，但是如果您只为一次查找构建 trie，那么它可能不是最快的方法......

Answer 2

List::Util Core 模块中的 first 函数可以查找前缀是否与字符串匹配。它搜索前缀列表，并在找到匹配项后立即返回。如果没有必要，它不会搜索整个列表：

first 返回第一个元素
BLOCK 的结果是真值。如果
BLOCK 永远不会返回 true 或 LIST 是
空则返回 undef。

Answer 3

你提出了一个有趣的问题，但是当我出去寻找这样的东西时（例如在 List::MoreUtils 中），我不断地回想起，这与 有什么不同grep。这就是我基于 grep 的基本实现。如果您不介意搜索整个列表，或者想要所有匹配项，这里是一个示例：

#!/usr/bin/perl

use strict;
use warnings;

my @prefixes = qw/ pre1 pre2 pre3 /;

my $test = 'pre1fixed';
my @found = grep { $test =~ /^$_/ } @prefixes;

print "$_ is a prefix of $test\n" for @found;

我也认为必须有某种方法可以使用智能匹配运算符 ~~ 来执行此操作以短路的方式。另外，正如 toolic 指出的，List::Util 函数也可以用于此目的。这会在找到匹配项后停止搜索。

#!/usr/bin/perl

use strict;
use warnings;

use List::Util qw/first/;

my @prefixes = qw/ pre1 pre2 pre3 /;

my $test = 'pre1fixed';
my $found = first { $test =~ /^$_/ } @prefixes;

print "$found is the prefix of $test\n";

我知道的唯一算法是 Aho-Corasick将其作为练习留给读者（即我不知道），看看这是否对您有帮助。我看到有一个模块 (Algorithm::AhoCorasick）。我还相信我在某处读到过，在某些情况下，这个结构和 trie 结构是在 Perl 的匹配中实现的。也许有人知道我在哪里读到的？编辑：在关于匹配替代方案的SO问题中找到它