KMP算法以及代码实现

题目描述

leetcode: 28.实现strStr()

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

示例：

input：haysteack=“aabaabaaf” needle= “aabaaf”
output: 3

KMP算法

暴力求解两个for循环，复杂度O(m*n)。KMP算法利用前缀表，获取已经匹配的文本内容，避免从头匹配。前缀表记录最长相等前后缀，用于模式串与主串不匹配时，回退到对应位置。

求取前缀表

前缀表说明

前（后）缀定义：不包含最后（第一）一个字母，且以首（尾）字母开头（结尾）的子串，aabaaf为例：

前缀：a aa aab aaba aabaa

后缀： f af aaf baaf abaaf

前缀表记录了所有子串最长相等前后缀长度，aabaaf为例：

字串包括：a aa aab aaba aabaa aabaaf

• a： 无先后缀，0
• aa： 前缀a（第一个a）和后缀a（第二个a） 相等， 1
• aab： 无相等前后缀， 0
• aaba：前缀a(第一个a)后缀a（最后一个a）相等，1
• aabaa：前后缀aa， 2
• aabaaf： 0

生成前缀表，记为next数组：

a	a	b	a	a	f
0	1	0	1	2	0

前缀表计算

初始化前缀表，并定义遍历下标i,j,其中i表示模式串中当前计算的位置，j表示与之匹配的前缀末尾：

a	a	b	a	a	f
0
	i
j

状态1：若needle[i] != needle[j]则 j回退， j = next[j-1]。若仍不相等，则继续回退。若相等或j = 0，则进入状态2。

例如，对于：

a	a	b	a	a	f
0	1	0	1	2
					i
		j

此实，i = 5，j = 2 ，needle[5] != needle[2]， j = next[1 - 1] = 1

a	a	b	a	a	f
0	1	0	1	2
					i
	j

仍不相等，继续回退 j = next[1-1] = 0，则进入状态2

状态2：若needle[i] == needle[j]则 next[i++] = ++j

例如对于初始状态：

a	a	b	a	a	f
0
	i
j

i = 1， j = 0, needle[1] == needle[0]，则j = 0 + 1,need[1] = 1, i = 1 + 1

a	a	b	a	a	f
0	next[1] = 1
		i = 1 + 1
	j = 0 + 1

匹配过程

模拟匹配

状态1：初始状态：i, j = 0, 0

主串	a	a	b	a	a	b	a	a	f
	i
模式串	a	a	b	a	f
	j

状态2：当主串与模式串匹配时（haysteack[i]==needle[j]），i++,j++

主串	a	a	b	a	a	b	a	a	f
	i	→	→	→	i
模式串	a	a	b	a	a	f
	j	→	→	→	j

状态3：当主串与模式串不匹配时（haysteack[i]!=needle[j]）。 j取前缀表前一位的值（j = next[j-1]）。若仍不相等且j>0，则继续回退。若不相等且j = 0，则i++。

例如：

主串	a	a	b	a	a	b	a	a	f
						i
模式串	a	a	b	a	a	f
						j

此时i = 5, j = 5, haysteack[5]!=needle[5]，j取前缀表前一位的值j=next[5-1] = 2

主串	a	a	b	a	a	b	a	a	f
						i
模式串	a	a	b	a	a	f
			j

变为状态2，继续匹配，直至匹配完成

若直至 j = 0 仍不相等，则i++。例如：

主串	a	a	b	a	a	d	a	a	f
						i
模式串	a	a	f
	j=0	←	j

则i++，继续匹配

主串	a	a	b	a	a	d	a	a	f
							i
模式串	a	a	f
	j

代码实现

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def getNext(s: str) -> List[int]:
            # 求取next数组
            next = [0] * len(s)
            j = 0
            for i in range(1, len(s)):
                while j > 0 and s[i] != s[j]:
                    j = next[j - 1]
                if s[i] == s[j]:
                    j += 1
                next[i] = j
            return next
        # 模式串为0时，返回0，满足indexOf()函数
        if len(needle) == 0:
            return 0
        next = getNext(needle)
        i, j = 0, 0
        # 开始匹配
        while i < len(haystack) and j < len(needle):
            if haystack[i] == needle[j]:
                i += 1
                j += 1
            elif j:
                j = next[j - 1]
            else:
                i += 1
        if j == len(needle):
            return i - j
        return -1