距离上次更新本文已经过去了 386 天，文章部分内容可能已经过时，请注意甄别

参考《代码随想录》。

1. 介绍

KMP 算法是解决字符串问题时比较常用的一个算法，它可以将暴力破解法的时间复杂度 O(N^2) 降低到 O(M+N)，效率有不错的提升。

KMP 算法由 Knuth、Morris 和 Pratt 三位学者发明，也因此得名 KMP。

1.1 next 前缀表

KMP 算法的核心是 next 数组，实际上是一个前缀表：记录下标 i（包括 i）之前的字符串中有多长的相同前后缀。

首先我们要明确前缀和后缀的概念：除了最后一个字符的字符串其余部分都可称之为前缀；除了第一个字符的字符串其余部分都可以称之为后缀。

plaintext
1
2
3
4
5
6
7
8
9
10
字符串：abba
最长前缀：abb
最长后缀：bba

字符串：aa
最长前缀：a
最长后缀：a

字符串：a
没有前缀和后缀

相同前后缀就是看前缀和后缀的相同部分；比如字符串 abba，前缀和后缀中只有字符串 a 是相同的，所以这个字符串的最长相同前后缀只有 1。

而 KMP 算法中的 next 数组，就是存放这个最长相同前后缀数量的。以字符串 aabaaf 为例

下标字符串最大相同前后缀
0a0
1aa1
2aab0
3aaba1
4aabaa2
5aabaaf0

对 aabaaf 字符串而言，最终得到的 KMP 算法 next 数组存放的就是 {0,1,0,1,2,0}，这个数组就是该字符串的前缀表。

1.2 next 数组的作用

那么这个 next 数组有什么作用呢？给出一个示例题目：让你在 aabaabaaf 中查找是否包含子字符串 aabaaf；

image.png

假设我们使用暴力法，当匹配到最后一个字符不相同时，会将源串下标 + 1，然后重新匹配子串。

但仔细观察你会发现，虽然这里源字符串和子串的最后一个字符 f 不匹配，但前面三个 aab 是已经匹配上的，我们完全可以从这个已经匹配上的字符串往后找，会发现最终可以找到子字符串 aabaaf。

image.png

next 数组就是用来解决这个问题的。当发现不匹配时，回溯到当前位置前一个的 next 数组中所对应元素的下标位置。下图中 f 是下标 5，那么就需要回溯到 next[5-1] 的下标处，即回溯到子串中的下标 2 位置，重新开始匹配。

image.png

此时会发现下标 2 的位置和当前源串的字符相同，继续往后匹配子串，能找到完整的子串。

image.png

通过 next 数组，把原本需要重新遍历的方式改为从上一个可以被匹配的位置重新开始匹配，就节省了时间。

1.3 为什么？

因为前缀表记录了最长相同前后缀的信息，当我们匹配不上的时候，找到前一个下标对应前缀表内的数据，就能得到当前字符以前的字符串是否有相同的前缀。

plaintext
1
2
3
下标数 0 1 2 3 4 5
字符串 a a b a a f
前缀表 0 1 0 1 2 0

当 f 匹配不上的时候，前一位在前缀表中为 2，代表往前一共有 2 个字符（后缀），和整个字符串的前 2 位是相同的（即 aabaa 里面后缀的 aa 和前缀的 aa 相同，这里的前缀 aa 也是字符串的起始两个字符）。

这能告诉我们，刚刚匹配的字符串中，后缀部分匹配成功了 2 个 aa（不然也走不到 f 这里来），可以把这个后缀的 2 个 aa 当作前缀的 2 个 aa 来处理，而指针只需要回溯到前缀 aa 的下一个字符重新开始匹配即可，对于数组而言，下一个字符的下标就是前缀表中的数字。

image.png

1.4 获取一个字符串的 next 数组

获取 next 数组有几种实现方式

  • 将前缀表中的数据全部减一；
  • 将前缀表中的数据整体右移一位；
  • 直接使用前缀表；

个人更加喜欢直接使用前缀表的方式，因为原理就是这么学的，直接使用前缀表也比较好动懂一些。构造前缀表的代码如下，这个代码的逻辑可能没有那么好懂，最好是想办法背下来！

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void getNext(int* next,const std::string& s)
{
	int j = 0;
	next[0] = 0; // 初始化next数组第一位（第一位是不存在前缀和后缀，肯定为0）
	for(int i=1;i<s.size();i++) //遍历要从字符串第二位开始
	{
		// 后续需要取j-1作为下标的操作，所以j必须大于0
		// 当j和i的字符二者不匹配的时候，就需要往前回溯
		while(j>0 && s[i] != s[j])
		{
			j = next[j-1]; // 回溯到前一位下标在next数组中的元素
		}
		// 二者匹配，j+1
		if(s[i] == s[j])
		{
			j++;
		}
		// 赋值next数组
		next[i] = j;
	}
}

测试一下，成功获得刚刚计算出来的前缀表

cpp
1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
	string test = "aabaaf";
	int next[10];
	getNext(next, test);
	for (int i = 0; i < test.size(); i++)
	{
		cout << next[i] << " ";
	}
	cout << "\n";
	return 0;
}

输出

plaintext
1
0 1 0 1 2 0

2.leetcode-28 - 找到子串并返回起始下标

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

题目：给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

这道题就是学习 KMP 算法的经典题目，思路前文已经描述过了，这里只给出代码。

cpp
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
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public:
    void getNext(int* next,const std::string& s)
    {
        int j = 0;
        next[0] = 0; // 初始化next数组第一位（第一位是不存在前缀和后缀，肯定为0）
        for(int i=1;i<s.size();i++) //遍历要从字符串第二位开始
        {
            // 后续需要取j-1作为下标的操作，所以j必须大于0
            // 当j和i的字符二者不匹配的时候，就需要往前回溯
            while(j>0 && s[i] != s[j])
            {
                j = next[j-1]; // 回溯到前一位下标在next数组中的元素
            }
            // 二者匹配，j+1
            if(s[i] == s[j])
            {
                j++;
            }
            // 赋值next数组
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        // 子串为空肯定找不到
        if(needle.size() == 0){
            return -1;
        }

        int next[needle.size()];
        getNext(next,needle);
        int j=0;
        for(int i=0;i<haystack.size();i++)
        {
            while(j>0 && haystack[i] != needle[j])
            {
                j = next[j-1]; // 往前回溯一位
            }
            if(haystack[i] == needle[j]){
                j++;
            }
            // j已经超出大小，说明子串完全匹配，成功。
            if(j>=needle.size())
            {
                return (i - needle.size() + 1); // 返回子串的起始下标
            }
        }
        return -1;//没找到
    }
};

题解通过

image.png

3.leetcode-459 - 重复的子字符串

3.1 题目

459. 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

plaintext
1
2
3
4
5
6
7
8
示例 1:
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:
输入: s = "aba"
输出: false

3.2 解释

这道题同样可以用 KMP 算法来解决，因为前缀表间接包含了当前字符串是否能通过某个子串重复构成的功能。

假设目标字符串长度为 len，前缀表为 next 数组，那么 next[len-1] 是前缀表的最后一位，保存了完整字符串的最长相同前后缀的长度。

len

如果字符串的长度能 整除 字符串的长度减去 next[len-1]，则代表字符串能被重复的子串循环构成！

观察下面这个字符串和它的前缀表，最后一位的数据是 6，整个字符串的长度是 9，这代表，整个字符串中，最长相同前缀和后缀有 3 个字符是重合的部分，且字符串的前缀 3 个字符和后缀 3 个字符都和中间这个重复的三个字符相同！

plaintext
1
2
3
4
5
6
字符串 abcabcabc
前缀表 000123456

源串 abcabcabc
前缀 abcabc
后缀    abcabc

如下所示，中间三个字符 abc 是在前后缀中重合的，而前缀第一个 abc 又能和后缀的前一个 abc 匹配上，后缀的末尾 abc 又能和中间重复的部分匹配上，则代表整个字符串就是由 abc 循环构成的。

image.png

而依据上述的公式计算，9/(9-6) = 3，可以被整除，即符合循环构成的条件！

描述的可能有点抽象，估计过几天回头看我自己也看不懂了……🤣

3.3 代码

cpp
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
class Solution {
public:
    void getNext(int* next,const std::string& s)
    {
        int j = 0;
        next[0] = 0; // 初始化next数组第一位（第一位是不存在前缀和后缀，肯定为0）
        for(int i=1;i<s.size();i++) //遍历要从字符串第二位开始
        {
            // 后续需要取j-1作为下标的操作，所以j必须大于0
            // 当j和i的字符二者不匹配的时候，就需要往前回溯
            while(j>0 && s[i] != s[j])
            {
                j = next[j-1]; // 回溯到前一位下标在next数组中的元素
            }
            // 二者匹配，j+1
            if(s[i] == s[j])
            {
                j++;
            }
            // 赋值next数组
            next[i] = j;
        }
    }

    bool repeatedSubstringPattern(string s) {
        int next[s.size()];
        getNext(next,s);
        size_t len = s.size();
        if(next[len-1] != 0 && (len%(len-next[len-1])) == 0){
            return true;
        }
        return false;
    }
};

image.png

The end

KMP 算法有点不好理解，把 next 数组的构建背下来就差不多得了……