KMP算法

Posted on Edited on

虽然python c++中都会有字符串查找的库函数 在刷题的过程中遇到了查找子串的问题 通常直接调用函数就可以解决 但是KMP作为十分重要的算法 很大概率会在面试中手撕 虽然依然要掌握

题干：给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

KMP算法 一个很重要的思想就是 当两指针对应的字符不匹配时，子串的指针不需要重新回到子串起始重新匹配 而是根据next数组 跳转到已经匹配过的内容中，从而实现降低时间复杂度 KMP的时间复杂度是log（m+n）

求next数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def getnext(self,next,s):
    """
    求next数组分成三步：
    1.初始化
    2.判断前后缀不同的情况
    3.判断前后缀相同的情况
    4.更新next数组
    """
    j=0
    next[0]=0
   	for i in range(1,len(s)):  # 记住这里i是从1开始的！！！
        while j>0 and s[i]!=s[j]:
            j=next[j-1]
        if s[i]==s[j]:
            j+=1
        next[i]=j
    return next

next数组是根据needle子字符串来得到的 而不是原字符串！

完整KMP代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def getnext(self,next,s):
        j=0
        next[0]=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
   	def kmp(self,haystack,needle):
        next=[0]*len(neddle)
        next=self.getnext(next,needle)
        j=0
        for i in range(len(haystack)):
            while j>0 and haystack[i]!=needle[j]:
                j=next[j-1]
            if haystack[i]==needle[j]:
                j+=1
            if j==len(needle):
                return i-len(needle)+1
        return -1