string - 查找给定句子中出现的单词

Question

我有单词列表。字数约为100万。

我在运行时有字符串，我必须检查列表中的哪个单词存在于字符串中并返回该单词（不需要返回句子中出现的所有单词，返回第一个也足以满足要求）。

一种解决方案是逐个检查字符串中的所有单词，但效率低下。

有人可以指出任何有效的方法吗？

Answer 1

使用Knuth-Morris-Pratt算法。虽然一百万字也不算多。您还可以将文本正文转换为Trie结构，然后使用它来检查您的搜索列表。有一种特殊的 Trie，称为后缀树，专门用于全文搜索。

Answer 2

将您的单词列表放在树或哈希表中。

Answer 3

除非您的单词列表是有序的（或插入到有序二叉树等有效的数据结构中）以执行二进制搜索，否则您提出的解决方案是最有效的解决方案。