首页 > 代码库 > 字符串匹配的sunday算法
字符串匹配的sunday算法
sunday算法核心思想：启发式移动搜索步长！
SUNDAY 算法描述：
字符串查找算法中，最著名的两个是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。这里介绍一种比BM算法更快一些的sunday查找算法。
例如我们要在"substring searching algorithm"查找"search"，刚开始时，把子串与文本左边对齐：
substring searching algorithm
search
^
结果在第二个字符处发现不匹配，于是要把子串往后移动。但是该移动多少呢？这就是各种算法各显神通的地方了，最简单的做法是移动一个字符位置；KMP是利用已经匹配部分的信息来移动；BM算法是做反向比较，并根据已经匹配的部分来确定移动量。这里要介绍的方法是看紧跟在当前子串之后的那个字符（上图中的 ‘i‘)。
显然，不管移动多少，这个字符是肯定要参加下一步的比较的，也就是说，如果下一步匹配到了，这个字符必须在子串内。所以，可以移动子串，使子串中的最右边的这个字符与它对齐。现在子串‘search‘中并不存在‘i‘，则说明可以直接跳过一大片，从‘i‘之后的那个字符开始作下一步的比较，如下图：
substring searching algorithm
search
^
比较的结果，第一个字符就不匹配，再看子串后面的那个字符，是‘r‘,它在子串中出现在倒数第三位，于是把子串向前移动三位，使两个‘r‘对齐，如下：
substring searching algorithm
search
^
哈！这次匹配成功了！回顾整个过程，我们只移动了两次子串就找到了匹配位置，是不是很神啊?!可以证明，用这个算法，每一步的移动量都比BM算法要大，所以肯定比BM算法更快。
因此，对于leetcode上的解题：
https://leetcode.com/problems/implement-strstr/
Implement strStr().Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
完整的Python代码如下：
class Solution(object): def strStr(self, haystack, needle): """ :type haystack: str :type needle: str :rtype: int REFER: http://blog.csdn.net/kankan231/article/details/22406823 """ char_pos = dict() for i, ch in enumerate(needle): char_pos[ch] = i i = 0 len1 = len(haystack) len2 = len(needle) while i <= len1 - len2: found = True for j, ch in enumerate(needle): if haystack[i+j] != ch: found = False if (i+len2) < len1: if haystack[i+len2] not in char_pos: i += (len2+1) else: i += (len2-char_pos[haystack[i+len2]]) else: return -1 break if found: return i return -1
参考：http://blog.csdn.net/kankan231/article/details/22406823
字符串匹配的sunday算法