【算法】KMP算法

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

参考《代码随想录》。

1.介绍

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

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

1.1 next 前缀表

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

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

字符串：abba
最长前缀：abb
最长后缀：bba

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

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

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

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

下标	字符串	最大相同前后缀
0	a	0
1	aa	1
2	aab	0
3	aaba	1
4	aabaa	2
5	aabaaf	0

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

1.2 next数组的作用

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

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

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

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

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

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

1.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的下一个字符重新开始匹配即可，对于数组而言，下一个字符的下标就是前缀表中的数字。

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

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

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

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

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 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;
}

输出

0 1 0 1 2 0

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

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

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

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

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;//没找到
    }
};

题解通过

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

3.1 题目

459. 重复的子字符串

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

示例 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个字符都和中间这个重复的三个字符相同！

字符串 abcabcabc
前缀表 000123456

源串 abcabcabc
前缀 abcabc
后缀    abcabc

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

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

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

3.3 代码

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;
    }
};

The end

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