有效检查给定字符串是否与一组前缀之一匹配 [英] Check if given string matches one of set of prefixes, effectively

问题描述

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

What algorithm to use to check if a given string matches one of set of prefixes, and which prefix from that set?

其他变化形式:给定路径和一组目录，如何检查路径是否在一组目录中(假设没有符号链接，或者它们无关紧要)?

Other variation: given path and a set of directories, how to check if path is in one of set of directories (assuming that there are no symbolic links, or they do not matter)?

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

I'm interested in description or name of algorithm, or Perl module which solves this (or can be used to solve this).

修改
解决方案的加分点，可以有效地找到字符串集(目录集)之间的'是'关系的前缀

Edit
Bonus points for solution which allow to effectively find 'is prefix of' relation between set of strings (set of directories)

例如，给定目录集:foo, foo/bar, foo/baz, quux, baz/quux, baz/quux/plugh该算法将发现foo是foo/bar和foo/baz的前缀，而baz/quux是baz/quux/plugh的前缀...希望没有O(n ^ 2)时间.

For example, given set of directories: foo, foo/bar, foo/baz, quux, baz/quux, baz/quux/plugh the algorithm is to find that foo is prefix of foo/bar and foo/baz, and that baz/quux is prefix of baz/quux/plugh... hopefully without O(n^2) time.

推荐答案

有效的方法是使用Trie:

The efficient way to do this would be using a Trie:

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

在CPAN上有一个针对它的软件包:

There is a package for it on CPAN:

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

(虽然我自己从未使用过该软件包)

(never used that package myself though)

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

You need to consider your what operations need to be the most efficient. The lookup is very cheap in a Trie, but if you only build the trie for one lookup, it might not be the fastest way...

这篇关于有效检查给定字符串是否与一组前缀之一匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！