文章转自:https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0028.%E5%AE%9E%E7%8E%B0strStr.md
大佬公众号:代码随想录
来源
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。
KMP应用场景
KMP主要应用在字符串匹配上。
KMP的主要思想是【当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配】。
所以如何记录已经匹配的文本内容,是KMP的重点,也是next数组肩负的重任。
前缀表
next数组就是一个前缀表(prefix table)。
前缀表是用来回溯的,它记录了模式串与主串(文本串)不匹配的时候,模式串应该从哪里开始重新匹配。
例如:
要在文本串(主串):aabaabaafa中查找是否出现过一个模式串:aabaaf。
如下所示:
可以看出,文本串中第六个字符b 和 模式串的第六个字符f,不匹配了。如果暴力匹配,会发现不匹配,此时就要从头匹配了。
但如果使用前缀表,就不会从头匹配,而是从上次已经匹配的内容开始匹配,找到了模式串中第三个字符b继续开始匹配。
此时就要问了前缀表是如何记录的呢?
首先要知道前缀表的任务是当前位置匹配失败,找到之前已经匹配上的位置,在重新匹配,此也意味着在某个字符失配时,前缀表会告诉你下一步匹配中,模式串应该跳到哪个位置。
那么什么是前缀表:下表i之前(包括i)的字符串中,有多大长度的相同前缀后缀。
最长相等前后缀
文章中字符串的前缀是指【不包含最后一个字符的所有以第一个字符开头的连续子串】;
后缀是指【不包含第一个字符的所有以最后一个字符结尾的连续子串】。
前缀表要求的就是相同前后缀的长度。
为什么一定要用前缀表
这就是前缀表那为啥就能告诉我们 上次匹配的位置,并跳过去呢?
回顾一下,刚刚匹配的过程在下表5的地方遇到不匹配,模式串是指向f,如图:
然后就找到了下标2, 指向b,继续匹配,如图:
下表5之前这部分的字符串(也就是字符串aabaa)的最长相等的前缀 和 后缀字符串是 子字符串aa ,因为找到了最长相等的前缀和后缀,匹配失败的位置是后缀子串的后面,那么我们找到与其相同的前缀的后面从新匹配就可以了。
所以前缀表具有告诉我们当前位置匹配失败,跳到之前已经匹配过的地方的能力。
如何计算前缀表
如图:
子串a的最长相同前后缀的长度为0,这是默认的(参考前缀后缀定义)。
长度为2的子串aa, 前缀为a(下标为0的a),后缀也为a(下标为1的a),相同前后缀长度为1,所以子串aa的最长相同前后缀长度为1。
长度为3的子串aab,前缀为aa, 后缀为ab,前后缀不相同,因此最长相同前后缀为0。
后面以此类推:
长度为前4个字符的子串aaba,最长相同前后缀的长度为1。
长度为前5个字符的子串aabaa,最长相同前后缀的长度为2。
长度为前6个字符的子串aabaaf,最长相同前后缀的长度为0。
那么把求得的最长相同前后缀的长度就是对应前缀表的元素,如图:
可以看出前缀表里的数值代表着就是:当前位置之前的子串有多大长度相同的前缀后缀。
再来看一下如何利用 前缀表找到 当字符不匹配的时候应该指针应该移动的位置。如动画所示:
找到不匹配的位置,那么此时就要看它前一个字符的前缀表的数值是多少。
为什么要看前一个字符的前缀表的数值呢?
因为要找前面字符串的最长相同的前缀和后缀。
所以要看前一位的 前缀表的数值。
前一个字符的前缀表的数值是2, 所有把下表移动到下表2的位置继续比配。可以再反复看一下上面的动画。
最后就在文本串中找到了和模式串匹配的子串了。
前缀表有什么问题
会有这样一种情况:
看这个位置红框的位置,如果要找下表1 所对应 前缀表里的数值的时候,前缀表里的数值依然是1,然后就要跳到下表1的位置,如此就「形成了一个死循环」。
如何怎么避免呢?
就把前缀表里的数值统一减一, 开始位置设置为-1 。如下:
为什么不会有这种情况呢?下标为1的前缀表数值减一后的还是1呢?
下标为1, 说明只有两个字符,根据前缀后缀的定义:
前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串;
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
我们可以知道长度为2的字符最长相等前后缀不可能大于1。
因此通过将前缀表中数值减一来避免死循环!
最后得到的新前缀表在KMP算法里通常用一个next数组来表示。
注意这个next数组就根据模式串求取的。
next数组
next数组就是通过前缀表减一得到的。
有了next数组,就可以根据next数组来 匹配文本串s,和模式串t了。
匹配过程动画如下:
构造next数组
我们定义一个函数getNext来构建next数组,函数参数为指向next数组的指针,和一个字符串。 代码如下:
void getNext(int* next, const string& s);
构造next数组其实就是计算模式串s,前缀表的过程。 主要有如下三步:
- 初始化
- 处理前后缀不相同的情况
- 处理前后缀相同的情况
- 初始化
定义两个指针 i 和 j ,j 指向前缀起始位置,i 指向后缀起始位置。
然后还要对next数组进行初始化赋值,如下:
int j = -1; //前缀表统一减一
next[0] = j; //第一个字符的next值默认为-1(0 - 1)
next[i] 表示 i(包括i)之前最长相等的前后缀长度(其实就是j)
为什么是j?
因为j 指向前缀起始位置,i 指向后缀起始位置, 当前后缀匹配时i ,j会同时后移直至匹配完成。匹配完成后j 则为前后缀相等时的前缀长度。
所以初始化next[0] = j 。
- 处理前后缀不相等的情况
因为j初始化为-1,那么i就从1开始,进行s[i] 与 s[j+1]的比较。
所以遍历模式串s的循环下标i 要从 1开始,代码如下:
for (int i = 1; i < s.size(); i++)
如果 s[i] 与 s[j+1]不相同,也就是遇到 前后缀末尾不相同的情况,就要向前回退。
怎么回退呢?
next[j]就是记录着j(包括j)之前的子串的相同前后缀的长度。
那么 s[i] 与 s[j+1] 不相同,就要找 j+1前一个元素在next数组里的值(就是next[j])。
所以,处理前后缀不相同的情况代码如下:
while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
j = next[j]; // 向前回退
}
- 处理前后缀相同的情况
如果s[i] 与 s[j + 1] 相同,那么就同时向后移动i 和j 说明找到了相同的前后缀,同时还要将j(前缀的长度)赋给next[i], 因为next[i]要记录相同前后缀的长度。
代码如下:
if (s[i] == s[j + 1]) { // 找到相同的前后缀
j++;
}
next[i] = j;
整体代码如下:
void getNext(int* next, const string& s)
{
int j = -1;
next[0] = j;
for (int i = 1; i < s.size(); i++)
{
//不相等情况
while (j >= 0 && s[i] != s[j + 1]) //j 初始值为-1, 所以后面需要和s[j + 1]比较,又因为i从1开始,不匹配时无需回退,所以j >=0
{
j = next[j]; //j回退
}
//相等情况
if (s[i] == s[j + 1])
{
//i 和j同时后移继续匹配
j++;
}
//更新next数组
next[i] = j;
}
}
代码构造next数组的逻辑流程动画如下:
时间复杂度分析
其中n为文本串长度,m为模式串长度,因为在匹配的过程中,根据前缀表不断调整匹配的位置,可以看出匹配的过程是O(n),之前还要单独生成next数组,时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。
暴力的解法显而易见是O(n * m),所以KMP在字符串匹配中极大的提高的搜索的效率。
文章出自:https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0028.%E5%AE%9E%E7%8E%B0strStr.md
原文大佬公众号:代码随想录