字符串匹配KMP算法

  1. 时间复杂度为O(n+m)，其中n为模式串的长度，m为待匹配串的长度。
  2. 空间复杂度为O(m)，其中m为待匹配串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        next = self.build_next(needle)
        i = 0
        j = 0
        while i < len(haystack):
            if haystack[i] == needle[j]:
                i += 1
                j += 1
            elif j == 0: # 如果j为0，则i+1，继续匹配
                i += 1
            else: # 如果j不为0，则j=next[j-1]，继续匹配
                j = next[j-1]
            
            if j == len(needle): 
                return i - j
        
        return -1

    def build_next(self, patt):
        next = [0] * len(patt)
        prefix_len = 0
        i = 1

        while i < len(patt):
            if patt[prefix_len] == patt[i]: # 如果当前字符与前缀字符相同，则前缀长度+1，i+1
                prefix_len += 1
                next[i] = prefix_len
                i += 1
            elif prefix_len != 0: # 如果当前字符与前缀字符不同，则前缀长度回退到上一个相同字符的位置
                prefix_len = next[prefix_len-1] 
            else:
                next[i] = 0
                i += 1

        return next