查找匹配子字符串列表的行

Question

查找匹配子字符串列表的行

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 的建议功能。

谢谢

- John Smith

使用Trie树是愚蠢的。可以使用已知的字符串匹配算法，如Boyer-Moore或正则表达式。 - leppie

你也可以使用KMP算法进行字符串匹配。https://zh.wikipedia.org/wiki/KMP%E7%AE%97%E6%B3%95 - tdedecko

我原本并没有想到要使用这些“命名”的算法。我以为解决方案会是我能够即兴想出来的东西。是的，这里发布的算法是用简单的结构发明的，但在面试中想出它们的可能性很小。如果面试官期望我使用Boyer-Moore、KMP等算法，我认为这不是一个好问题。 - John Smith

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jim Mischel · Accepted Answer

你可以使用正则表达式。例如，正则表达式 oo|goog|app 可以实现这一点。

如果你有大量的子字符串并且需要搜索大量文本，那么你可以使用类似 Aho-Corasick 字符串匹配算法的东西。

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

关于您对问题适当性的评论，它可能并不是旨在得到一个“正确”的答案，而是想了解您如何思考问题。例如，使用标准的字符串搜索算法需要与MxN成比例的时间，其中M是要搜索的字符串数，N是要查找的子字符串数。正则表达式解决方案会更快，因为您只需要在要搜索的每个字符串上运行一次正则表达式即可。Aho-Corasick算法更快，因为它的状态机可以在单次遍历中找到所有匹配项。您使用的方法取决于许多因素，包括您有多少字符串和子字符串，您需要多频繁地运行此操作以及您实现解决方案的时间。这是一个很好的问题，可以揭示您如何处理困难问题以及如何识别和评估潜在的解决方案。