前言
最初想写这篇文章的原因是在LeetCode上看到了一道实现strStr函数的题:
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
题目要求实现一个函数:
1 | public int strStr(String haystack, String needle) |
这个函数的两个参数名分别为haystack和needle,可能有人会疑惑为什么要用这么两个看着不相关的单词作为参数名,这里稍微解释下:英语有个口语叫”It’s a needle in a haystack”,直接意思就是草垛寻针,也就是大海捞针之意。一方面传达了我们这个函数的功能,同时可能也想凸现一下这个操作的复杂度吧,老外有时候就是喜欢整一些黑色幽默。
因此,在后文的介绍里,haystack就是操作源数据,needle就是我们要去搜索的目标。
其实有很多算法可以来实现字符串查找,暴力的BF算法,经典的KMP算法,BM算法,Sunday算法等等,就效率和实现难度上来说,Sunday算法应该是性价比最高的,效率高,容易理解,实现也比较简单。
Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是:在匹配过程中,模式串发现不匹配时,算法能跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率。
下面我们通过示例来理解一下Sunday算法的工作原理:
示例原理
Sunday采用模式匹配的思想,匹配失败时,选择haystack中参加匹配的最末尾字符的后一位字符作为参照字符,如果该字符在needle串中有出现,则将needle串中最后出现该字符的位置与参照字符位置对齐继续比较,否则直接跳过该匹配区域,从参照字符的下一位重新开始比较。
OK,这一段实在太长,可能不太好理解,简单粗暴,来举个例子:
说明:
场景一:对照字符在needle中存在
首先从前往后对needle和haystack串中参与比较的子串here
进行字符比较,发现第一个字符匹配失败,则找到haystack参与比较的子串末尾字符的后一个字符e
作为参照字符,然后我们在needle串中从后往前找到字符e
,然后将两者位置对齐,如下图所示:
场景二:对照字符在needle中不存在
对齐后我们继续对比needle串和haystack中新参与比较的子串ere e
,发现依然不匹配。我们找到比较子串的后一个字符v
作为参照字符,寻找v在needle串中最后出现的位置,显然needle串中并不存在字符v
,这种情况下,我们可以直接将主串游标跳到字符v
后继续下一轮比较。
重新对齐后,比较发现依然不匹配,继续找到下一个对照字符h
,h在needle串中有出现,满足上述场景一的条件,则找到h
在needle串中最后出现的位置与参照字符对齐,继续比较,发现匹配成功。
代码实现
该算法的Java实现
1 | public int Sunday(String haystack, String needle) { |
实际环境中可以根据needle串的约束对needle串进行预处理,提前建立好索引,提高查找效率。
总结
通过上文介绍不难发现,Sunday算法在处理重复字符少的场景效率会很高,因为每次都可以跳过比较多的字符,很大程度的减少了比较次数,综合来说,Sunday算法的平均时间复杂度为O(n),最差情况的时间复杂度为O(n * m).
- 本文作者: Aries Chen
- 本文链接: http://yoursite.com/2020/01/18/Sunday算法介绍及Java实现/
- 版权声明: 本博客所有文章除特别声明外,均采用MIT许可协议。转载请注明出处!