在字符串中查找字符串的典型算法是什么？

Question

我最近有一个面试问题是这样的:

给定一个大字符串(haystack),找到一个子串(针)？

我有点难过想出一个像样的解决方案.

处理此问题的最佳方法是什么,时间复杂度不高？

Answer 1

我喜欢Boyer-Moore算法.当您在大海捞针中找到大量针头时(例如,电子邮件语料库中的可能垃圾邮件模式),实施起来特别有趣.

Answer 2

您可以使用Knuth-Morris-Pratt算法,即O(n + m),其中n是"haystack"字符串的长度,m是搜索字符串的长度.

Answer 3

一般问题是字符串搜索 ; 根据应用程序的性质,有许多算法和方法.

一些高级索引数据结构也用于其他应用程序.后缀树在生物信息学中被大量使用; 在这里你有一个长引用文本,然后你有许多任意字符串,你想找到所有出现的.一旦建立了索引(即树),就可以非常有效地找到模式.

对于面试答案,我认为展示广度也更好.了解所有这些不同的算法以及它们最佳服务的具体目的可能比仅仅了解一种算法更好.

"对于面试答案,我认为最好也要表现出广度." 我不知道.你是不是应该知道这些问题？在现实生活中,您将在Internet上查找算法.在一次采访中,我希望有人能够提出像Brian或者paxdiablo show这样的实现,并能够解释那些表现不佳的情况. (2认同)