performance - 查找文本是否包含列表中的任何单词。哪个更快，为什么？

Question

可能有更好的解决方案，但我首先想到的是:

1) 对于列表中的每个单词，检查文本是否包含该单词2) 将单词存储在一个集合中。从另一组文本中存储单词(任何由空格分隔的东西 - 不必太准确)并检查 2 组的交集是否为空

我不知道哪个更好，或者它们是否差不多。

Answer 1

这就是集合匹配问题。

让 S 一组模式，T 您的文本，n 在 T 中找到的 S 中的元素数。然后 你可以在时间 O(|T| + |S| + n) [*] 使用 Aho–Corasick string matching algorithm 找到文本中 S 中所有元素的出现.

鉴于您只想找到第一次出现，执行时间在最坏的情况下减少到 O(|T| + |S|)，如果 S 足够小，它与文本长度成线性关系!

[*] |S|是集合中所有单词的长度