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

Question

这是一道面试题。

我有一个包含网址的文本文件，例如:

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 中的工作方式。

谢谢

Answer 1

您可以使用正则表达式。例如，表达式 oo|goog|app 就可以做到这一点。

如果您有大量子字符串并且要搜索大量文本，您可以使用类似 Aho-Corasick string matching algorithm 的方法。 .

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

关于您对问题适当性的评论，它可能不是为了获得“正确”答案而设计的，而是为了了解您如何看待问题。例如，使用标准字符串搜索算法所花费的时间与 MxN 成正比，其中 M 是要搜索的字符串数，N 是要查找的子字符串数。正则表达式解决方案会更快，因为您只需对要搜索的每个字符串运行一次正则表达式。 Aho-Corasick 算法更快，因为它的状态机在一次通过中找到所有匹配项。您使用的方法取决于许多因素，包括您有多少个字符串和子字符串、您必须多久运行一次以及您需要多少时间来实现该解决方案。这是一个很好的问题，可以揭示您如何处理难题以及如何识别和评估潜在的解决方案。