KMP算法——28. 找出字符串中第一个匹配项的下标

KMP算法

今天在做字符串匹配的问题的时候想起了KMP算法。真的很难理解，所以在这里进行一个整理。
KMP算法在字符串不匹配的时候提供了一种简单的方式，使得模式串不需要从头去遍历。
例如:
待匹配串s： aabaaf 使用i去遍历
模式串t：aabaab 使用j去遍历
我们使用for循环遍历i和j为5的时候，发现s[i] != s[j]，此时j需要回退到j = 2的位置。因为s和t有相同的字符串aa。

那么如何使得j回退到正确的位置，这里我们需要使用最长相等前后缀，用next来表示。

• 前缀：带首字母不带尾字母的连续子串
• 后缀：带尾字母不带首字母的连续子串

以以下字符串为例进行介绍：
a：没有最长相等前后缀, 0
aa: 前缀a等于后缀a，最长相等前后缀1
aab：后缀末尾b无匹配，0
aaba：前缀a等于后缀a，最长相等前后缀1
aabaa：前缀aa等于后缀aa，最长相等前后缀2
aabaab：前缀aab等于后缀aab，最长相等前后缀3
综上，当模式串是aabaab时，前缀表next = [0,1,0,1,2,3]。当我们发现aabaaf中指针指向f的时候不符合要求（不等于b），那我们就需要寻找前一位的next[4] = 2，查看相同的前缀（也就是aa）的后一位，指向2位置进行进一步的对比。

代码实现如下。其中，j表示为最长相等前后缀的后一个位置（方便进行比较），也是其长度。

1. 对于needle[i] == needle[j]，j的左侧位置中具有与j右侧某处到i相同的字符串（j为0时就是没有），此时j找后一个位置 j += 1。然后next[i] = j。
2. 当needle[i] ！= needle[j]，因为是连续字符串，就需要往前找。j找它前一个位置的最长相等前后缀的后一位置（表示为next[j - 1]），看看那个位置的元素是否与needle[i] 相等。不相等继续往前找，直到j = 0。这个思路与上面aabaaf和aabaab不匹配时候的查找方式相似。

def getNext(needle):
    next = [0] * len(needle)
    j = 0
    for i in range(1, len(needle)):
        while j > 0 and needle[i] != needle[j]:
            j = next[j - 1]
        if needle[i] == needle[j]:
            j += 1
        next[i] = j
    return next
1
2
3
4
5
6
7
8
9
10

完整代码如下：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:

        def getNext(needle):
            next = [0] * len(needle)
            j = 0
            for i in range(1, len(needle)):
                while j > 0 and needle[i] != needle[j]:
                    j = next[j - 1]
                if needle[i] == needle[j]:
                    j += 1
                next[i] = j
            return next

        next = getNext(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
                
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