检查关键字是否在字符串中

Question

我有一个关键字列表,我希望能够找到一个字符串是否包含任何这些关键字.现在我的解决方案需要O(n).有没有更快的方式进行此搜索而不循环每个关键字并进行比较/包含？

ie Keywords ="cat","hat","mat","bat","fat","sat","rat","pat","foo bar","foo-bar"String ="有盒子里的一只猫." 结果是这样的,因为"cat"匹配'keywords'中的一个单词

编辑:当我说O(n)时,我想我不太清楚.我的意思是说O(n)其中n =关键字的数量.

Answer 1

您可以使用Boyer-Moore，它涉及对字符串进行预处理，但您将无法击败 O(KN) 的最坏情况，其中 K 是关键字长度的总和，N 是长度字符串的。最好的情况当然是次线性的，但你不可能有最坏情况的次线性运行时间。

请注意，比较不是免费的。这不像您可以在 O(1) 中比较两个字符串来查看它们是否相等，您必须迭代字符。散列可以让您在恒定时间内获得需要比较的内容，但没有什么帮助，因为两个不同的字符串可以具有相同的散列。这并不是说散列不好，确实如此，但它不会改变最坏情况下的运行时复杂性。

最后，你需要比较角色，Boyer-Moore 提供了一个非常好的方法来做到这一点。当然，如果您使用某种基于哈希的构建，您也许能够在摊销常数时间内排除某些关键字，但这并不能改变这样的事实：在最坏的情况（以及许多其他情况）下，您'我们需要比较字符。

另请注意，根据我们对数据的假设以及我们如何构建索引结构，有可能实现非常好的实际运行时间。仅仅因为最坏情况的复杂性不是次线性的，并不意味着实际的运行时间不会很快。没有单一的简单或正确的解决方案，可以通过多种方式解决该问题。在信息检索方面，从来没有一个快速而肮脏的答案可以解决您的所有问题。