c++ - C++中的前缀匹配

Question

问题:

假设我有一个前缀列表:

[p1, p2, p3, ... pn] //Prefix List (strings)

我想知道字符串“target”是否具有上述任何前缀。

简单的解决方案示例:

bool contains_prefix(std::string target, vector<std::string> &prefixes)
{
    for (const auto& prefix : prefixes)
    {
       if (target.compare(0, prefix.length(), prefix)
           return true;
    }
    return false;
}

std::vector<std::string> prefixes{"car" , "auto" , "biscuits"};

bool test = contains_prefix("automobile", prefixes); //returns true
test = contains_prefix("biscu", prefixes); //returns false
test = contains_prefix("v", prefixes); //returns false (obviously)

因此，这个天真的解决方案有一个明显的不足，即它必须遍历列表中的每个项目。

有没有更快的方法来实现这种类型的前缀匹配？

我试过的东西:

1. 我尝试创建一个与 std::set 一起使用的比较对象，但集合需要严格的弱排序(通过 a>b 和 a'<'b 测试相等性，两者一定是假的)。所以 std::compare() 函数在这种情况下不起作用，因为检查一个字符串是否是另一个字符串的前缀是一种不对称关系。

2.我可以使用正则表达式来实现，但这并不能解决必须遍历每个元素的问题。

3.任何散列的数据结构都不适用于基于模式的匹配。

Answer 1

这取决于，你的目标是什么。

如果您有很多前缀而只有一个“目标”，那么您的代码是最佳的。

但是，如果您有很多“目标”，那么您可能需要考虑创建一个比前缀列表更智能的结构。我建议使用前缀树。 https://en.wikipedia.org/wiki/Trie

构建结构可能需要一些时间，但如果使用有很多“目标”，它就会得到返回。