3

这是一道面试题。

我有一个带有网址的文本文件,例如:

www.yahoo.com
www.google.com
www.apple.com
www.microsoft.com

我有一个子字符串列表,例如 oo、goog、app。如何找到与其中一个子字符串匹配的所有行?对于这个例子,我会:

www.yahoo.com
www.google.com
www.apple.com

面试官不喜欢逐行检查是否有任何子字符串出现在一行中。然后我说我们可以使用 trie,但这只有在子字符串的第一个字符与行中的第一个字符匹配时才有用,这类似于建议功能在 Google 中的工作方式。

谢谢

4

1 回答 1

2

你可以使用正则表达式。例如,表达式oo|goog|app会这样做。

如果您有大量子字符串并且要搜索大量文本,则可以使用Aho-Corasick 字符串匹配算法之类的东西。

有趣的是,蛮力方法(使用标准字符串匹配算法)和 Aho-Corasick 算法会为“www.google.com”(“oo”和“goog”)输出两个匹配项,但正则表达式解决方案会只输出一个。

关于您对问题适当性的评论,它可能不是为了获得“正确”的答案,而是为了看看您如何看待问题。例如,使用标准字符串搜索算法将花费与 MxN 成正比的时间,其中 M 是要搜索的字符串数,N 是要查找的子字符串数。正则表达式解决方案会更快,因为您只需对要搜索的每个字符串运行一次正则表达式。Aho-Corasick 算法仍然更快,因为它的状态机一次就可以找到所有匹配项。您使用的方法取决于许多因素,包括您拥有多少个字符串和子字符串,您必须多久运行一次,以及您需要多长时间来实施解决方案。它'

于 2013-01-31T05:59:44.917 回答