LeetCode28：实现 strStr()之KMP算法

---

前言

  本文主要是以 LeetCode28：实现strStr() 为例，为大家带来KMP算法的介绍，若有表述不当的地方，望指出。此外，本文所涉及的代码语言为Python。

---

一、LeetCode28：实现 strStr()

题目要求及示例

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

• 示例1：

输入：haystack = "hello", needle = "ll"
输出：2
1
2

• 示例2：

输入：haystack = "aaaaa", needle = "bba"
输出：-1
1
2

二、题目解法

2.1 暴力求解

  遍历字符串haystack，遍历要求是：找出haystack中与needle长度相等的所有子串；把遍历得到的每一个子串都与字符串needle进行比较，若相等则证明找到了，返回i，若循环结束仍未找到，返回-1。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        for i in range(n):
            if haystack[i:i+m] == needle:
                return i
        return -1
1
2
3
4
5
6
7

2.2 KMP算法求解

2.2.1 算法原理

  KMP算法主要用于解决字符串匹配问题，算法中涉及了一个小知识点是前缀表，它依赖于前缀表从而使得在不配的时候返回到适当的位置，避免从头开始。

1、什么是前缀表？

  拿一个经典的案例来讲，这里有一个文本串：aabaabaaf，一个模式串：aabaaf，目的是从文本串中找到模式串，并返回在文本串中找到模式串的第一个位置。前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
  在讲解前缀表之前，我们先去理解三个概念：前缀、后缀以及最长相等前后缀。

• 前缀：只包含首字母不包含尾字母的所有子串，如 aabaaf 的前缀有：a、aa、aab、aaba、aabaa；
• 后缀：只包含尾字母不包含首字母的所有子串，如 aabaaf 的后缀有：f、af、aaf、baaf、abaaf；
• 最长相等前后缀：子串中前缀和后缀相等的最大值，如aabaaf 的最长相等前后缀见下表：

• 前缀表：最长相等前后缀，即字符串aabaaf的前缀表是：[0 1 0 1 2 0] 。
  

2、前缀表的代码实现

<1> 前缀表与next数组

  其实next数组就是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。这并不涉及KMP的原理，只是遇见冲突不同的解决方法而已。本文中我们的next数组是前缀表统一右移一位之后的样子，遇见冲突时我们去找当前冲突的位置下标。

<2> next数组的构建

1. next数组初始化
2. 处理前后缀不相同的情况
3. 处理前后缀相同的情况
4. 更新next数组的值

a = len(needle)
def getNext(a, needle):
    next = [' ' for i in range(a)]
    j, k = 0, -1
    next[0] = k
    while j < a - 1:
        if k == -1 or needle[k] == needle[j]:
            k += 1
            j += 1
            next[j] = k
        else:
            k = next[k]
    return next
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2.2 完整题解代码

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        m, n = len(haystack), len(needle)
        if n == 0:
            return 0
        i, j = 0, 0
        next = self.getNext(n, needle)
        while (i<m and j<n):
            if j==-1 or needle[j]==haystack[i]:
                i+=1
                j+=1
            else:
                j=next[j]
        if j==n:
            return i-j
        else:
            return -1


    def getNext(self, n, needle):
        next = [' ' for i in range(n)]  # next的初始化
        j, k = 0, -1
        next[0] = k
        while (j < n-1 ) :
            if k==-1 or needle[k] == needle[j]: # 找到前缀表了
                k += 1
                j += 1
                next[j] = k
            else:
                k = next[k]
        return next
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

---

三、参考资料

• KMP算法原理视频讲解
• KMP算法实现视频讲解

四、小结

  到这里本文就结束了，感谢大家阅读，强烈推荐大家去 代码随想录 。刷题必备神器，冲冲冲！！！
  最后，觉得博主写的不错的，给博主点个赞鼓励一下吧！