字符串匹配

KMP 算法

主串指针始终向前，模式串指针根据 next 数组，每次遇到不匹配的情况则回退到前一位的 next 数组的值（当前位置最长相等前后缀的长度）。（利用已经匹配过的数组所获取的信息）（最长相等前后缀，为什么呢？模式串的前缀和先前匹配的子串后缀即为已经匹配过的数组所获取的信息，所以可以用最长相等前后缀来进行问题求解）

LeetCode 28. 找出字符串中第一个匹配项的下标，题解

最浅显易懂的 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
25
26
27
28
29
30
31
32
33
34
35
class Solution:  
    def strStr(self, haystack: str, needle: str) -> int:  
        # 求next数组  
        def build_next(pattern):  
            # 将后缀理解为主串，将前缀理解为子串  
            # 后缀i只向前移动  
            # 前缀j，当子串和主串不匹配时，回溯到next数组指向的位置  
            n = len(pattern)  
            next_arr = [0] * n  
            j = 0  # j 指向前缀末尾  
            for i in range(1, n):  # i 指向后缀末尾  
                # 字符不匹配，回退j到前一个匹配的位置  
                while j > 0 and pattern[i] != pattern[j]:  
                    j = next_arr[j - 1]  
                # 字符匹配，j前进  
                if pattern[i] == pattern[j]:  
                    j += 1  
                next_arr[i] = j  
            return next_arr  
          
        # KMP  
        next_arr = build_next(needle)  
        j = 0  # 子串指针  
  
        for i in range(len(haystack)):  
            # 当字符不同时，利用next数组回退  
            while j > 0 and haystack[i] != needle[j]:  
                j = next_arr[j - 1]  
            # 字符相同，j前进  
            if haystack[i] == needle[j]:  
                j += 1  
            # 匹配成功  
            if j == len(needle):  
                return i - j + 1  
        return -1

sunday 算法

1
...