概述
为什么大家总觉得KMP难?难的根本就不是这个算法本身。
在互联网上你可以见到八十种KMP算法的next数组定义和模式串回滚策略,把一切都懂得特别混乱。很多时候初学者的难点根本不在于这个算法本身,而是它令人痛苦的百花齐放的定义。
有的next数组从0下标开始,有的从1开始;有的表示不包括本字符的前面部分的真前后缀,有的表示包括本字符的的前后缀,有的回滚+1,有的不+1,而他们却总是忽略这些异同,自顾自地讲KMP的匹配问题。初学者看到这直接傻了眼:随便挑两个视频或者文章,他们的定义和递推手段都不一样,让理解难度雪上加霜。
下面我们来先从字符串匹配讲起,想一想什么样的next数组定义才最适合这个算法本身。
LeetCode 28:
给你两个字符串 haystack
和 needle
,请你在 haystack
字符串中找出 needle
字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle
不是 haystack
的一部分,则返回 -1
。
示例 :
输入:haystack = "sadbutsad", needle = "sad" 输出:0 解释:"sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ,所以返回 0 。
*注意*: 接下来我们将称呼haystack为主串,needle为模式串。
思路
最普通的暴力算法总是在匹配失败后将主串指针i回滚到开始匹配的位置,模式串指针j回滚到0,然后在一轮for循环结束后执行i++操作来跳过这个匹配失败的位置。来看看Code。
class Solution {
public:int strStr(string haystack, string needle) {const int n=haystack.size();const int m=needle.size();for(int i=0;i<n;i++){if(haystack[i]==needle[0])for(int k=i,j=0;k<n;k++){if(haystack[k]==needle[j])j++;else break;if(j==m)return i;}}return -1;}
};
来想一想:都回滚j了,为什么还回滚i?难道就因为有一个字符匹配失败了就放弃前面所有的努力吗?
至少在最后的失败字符之前,我们匹配成功了。这意味着:
模式串为pattern,主串为mainj
pattern[j] a b c a b f g√ √ √ √ √ ×main[i] a b c a b k v q x ti
至少在'f'字符与'k'字符对比之前,我们的匹配成功了。
这意味着,main函数的此前部分和pattern的此前部分一一对应,我们称之为str1。
这时候的一个独到之处就是:
在这段主串和模式串共同的[开头,失配位置)的子串str1中,匹配失败之前的任意位置,从这个位置开始,一直到匹配失败的位置之前他们都相同,这部分[任意位置,失配位置)的子串我们称为str2。
那我们可以有一个特殊的回滚模式串指针j的手段:不回滚到最开头,而是回滚到模式串的某个位置,在这个位置以前的部分模式串[开头,某位置)称为str3,它与str2相同。
结合例子感受一下:
模式串为pattern,主串为main┌str3┐ j<-------j
pattern[j] |a b c a b |f g| └str2┘| |√ √ √ √ √ || ┌str2┑|main[i] |a b c a b |k v q x t└----str1------┘i
这样看还是不够清晰,我们把j的移动形象理解成模式串的移动。
模式串为pattern,主串为main┌str3┐ j<-------j
pattern[j] a b c a b f g└str2┘ √ √┌str2┑main[i] a b c a b k v q x t└----str1-----┘ i
也就是说:在j倒退回某个位置后,这位置之前的模式串部分和主串部分是天生匹配的。
接下来我会用前后缀的语言代替“某某部分”:
//这是对前后缀的解释,如果你了解,可以跳过
对于一个字符串
begin enda b a c d x f a c a d----> ---->前缀 后缀 //*注意*:前后缀的字符顺序都是从前向后
前缀是从[begin,x]的任意子字符串 真前缀的x不等于end
后缀是从 [x,end] 的任意子字符串 真后缀的x不等于begin
归纳一下:
当匹配到主串i位置和模式串j位置,匹配失败时:
str2既是主串的[0,i)子串的一个后缀,又是模式串的[0,j)子字符串的一个后缀。
str3则是模式串中[0,j)子串的某个前缀,这个前缀与str2这个后缀相等。
因此,模式串中的str3能与模式串中的str2匹配,就意味着模式串中的str3与主串中的str2与是天生匹配的。
形象理解:
str3==str2
pattern -str3------str2-√√√√√√√√√√√√√√√×
main -----------str2-↓
pattern -str3------str2-√√√√√?
main -----------str2-
那按理来说,这是一个模式串的自匹配问题:对于模式串的每个位置j,都有[0,j)子串,都要找到他们的最长相同真前后缀。
因此问题就转化成了:
枚举模式串的每个下标j,求成它的[0,j)子字符串的最长相同真前后缀,这样,当在任意位置匹配失败时,都可以知道j的回滚位置了,而i从不回滚。
核心概念:前缀函数
网络上各种奇异搞笑的next数组定义的根本来源是他们没搞懂前缀函数和next数组的区别。
前缀函数是一个独立的算法函数概念,next数组只是它针对于KMP算法的特化版本。
1.前缀函数
它写作π[i]或PM[i]。
定义:
给定一个长度为n的字符串,其前缀函数被定义为一个长度为n的数组π[n](或:PM[n])。 其中π[i]的意义是:字符串的[0,i]子字符串的最长相同真前后缀。
故有:
j 0 1 2 3 4 5 6
string str[j] a b c a b c dπ[j] 0 0 0 1 2 3 0
这是标准的前缀函数定义,他长度就是n,下标起始位置就是0,其他的任何一种next数组都是他的特化版本。
*注意*:我通常使用j来作为next数组和模式串的索引。
2.next数组
在KMP匹配算法中,π数组变成了next数组,有如下几种方案:
1.考研版本
①模式串、主串和next数组下标统一从1开始计数。[j]表示第j个字符处,而不是索引0代表第1个字符。next[0]值为-1。
②next[j]表示原字符串{s[1]...s[j-1]}的最长相同真前后缀长度,它记录在了next[j]。next[j]的值不包括第j个字符。
③回滚代码:j=next[j]+1。
例如上文的"abcabcd",如果当j=7失配时,next[j]==3,那么j会从4开始继续匹配,跳过了123。
j 0 1 2 3 4 5 6 7
string str[j] n a b c a b c dnext[j] -1 0 0 0 0 1 2 3
//n通常储存字符串的长度信息。
*注意*:你还会见到next[0]=0,且next数组整体+1的版本,它是另一个考研版本,只是将回滚代码的+1操作融入了next数组中,回滚代码:j=next[j],此处不再赘述。
2.竞赛版本
事实上,在竞赛或者各大算法平台,字符串下标仍然从0开始,我们要为这个原则服务。
①字符串下标仍然从0开始,但我们仍然期望next数组下标从1开始。即主串与模式串从0开始,next数组从1开始,next数组长度比模式串大1,后续你会发现这样做的好处。
②next[j]表示原字符串*前j个字符*的最长相同真前后缀长度,它记录在了next[j],这里发生了错位。(next[0]=0,这样当j=0时执行回滚不会发生溢出,next[1]=0,第一个字符没有真先后缀)。
③回滚代码:j=next[j]。next数组错位的目的就是避免回滚代码发生+1-1的问题,这样能有效规避溢出。
例如上文的"abcabcd" ,如果当j=6失配时,next[j]==3,那么j会从3开始继续匹配,跳过了012。
即:j在某处失配时,它前面有j个字符,且这j个字符最长相同前后缀长度len储存在了next[j],可以快速访问next[j]得到j的回滚位置,回滚后恰好跳过len个字符。(我们总是期望在一轮for循环后j指向一个有待下一轮循环商榷的位置,不论是j++还是j=next[j],都是这样的。)
j 0 1 2 3 4 5 6 7
string str[j] a b c a b c d \0next[j] 0 0 0 1 2 3 0
算法过程
*注意*:我们会以竞赛版本的KMP进行讲解。它稍微更改就可以变成考研版。(比如insert函数)
构建next数组
构建next数组才是KMP本身具有难度的地方。
推论:字符串增加一个字符,它的最长相同真前后缀至多+1。这个不起眼的推论是构建的核心。
但是我们可以将其总结为3点:
①next[0]=0,next[1]=0,这两个直接无视。随后发生for循环int i=1,j=0。
i向前探索;j即用于为next[i+1]赋值,又作为下标索引与向前探索的i遥相呼应:[0,j]与[i-j,i]匹配。
因此j同时代表着:[0,i]的公共前后缀长度数值,也是与i这个前方洗标呼应的后方下标。
记得我们的定义是:next[j]表示原字符串*前j个字符*的最长相同真前后缀长度,i+1这个值才是[0,i]字符串的字符个数,因此j为next[i+1]赋值。
②当pattern[i]!=pattern[j],即位置i与位置j字符不匹配,通过while循环回滚j,如果仍失配,继续回滚,一直到j==0。
这一点是KMP的精髓所在:我们一边构建next数组,一边利用next数组回滚j。
这听起来很不可思议,但是注意:next数组是从前向后构建的,而回滚是向前的。这说明:我们在利用已经构建起的next数组进行回滚,而不会发生某种奇怪的冲突。
但是为什么用next数组回滚j呢?还记得next数组是干什么用的吗?它就是指示:当失配时,请从这里再试一试。不一定非要模式串与主串匹配才有失配,模式串自匹配时前缀不等于后缀也叫失配。我们回滚j就是期望将j回滚到可能与pattern[i]匹配的位置。
如果一直到j==0还失败,那就意味着不存在相同前后缀,那么为next[i+1]=j(即赋0值也是合理的了)
③判断pattern[i]是否等于pattern[j]。
如果因为j与i成功匹配而脱离while循环,那么j++,因为我们的最长相同前后缀+1。
void get_next(string&pattern,vector<int>&next){next[0]=0,next[1]=0;const int m=pattern.size();for(int i=1,j=0;i<m;i++){while(j&&pattern[j]!=pattern[i])j=next[j];if(pattern[j]==pattern[i])j++;next[i+1]=j;//赋值发生在j++之后,所以此处不用+1}}
匹配过程
匹配过程与构建过程极其类似。
主要是以下三点:
①当main[i]!=pattern[j],即在此处失配时,通过while循环回滚j,如果仍失配,继续回滚,一直到j==0。
②跳出while后判断main[i]是否等于pattern[j]。
由于脱离while要么是两者相等,要么不相等但j==0,那么:
if为真意味着:两者匹配成功,j++,i++。(两者在一轮循环后分别指向有待下一轮循环商榷的位置。)
if为假意味着:这一步就是判断出现j等于0且仍无法匹配的状况,那么认为这个i终究无法匹配,j停滞在0,随后放弃i的当前位置,i自增。
③判断j==m,这意味着完全匹配,返回i-m+1。(注意这里有个+1的细节:一轮for循环结束之前i++还未发生)
for(int i=0,j=0;i<n;i++){while(j&&main[i]!=pattern[j])j=next[j];if(main[i]==pattern[j])j++;if(j==m)return i-m+1;
}
return -1;
复杂度
时间复杂度:O(n+m)
空间复杂度:O(m)
n:主串长度
m:模式串长度
Code
class Solution {
public:void get_next(string&pattern,vector<int>&next){const int m=pattern.size();for(int i=1,j=0;i<m;i++){while(j&&pattern[j]!=pattern[i])j=next[j];if(pattern[j]==pattern[i])j++;next[i+1]=j;}}int strStr(string haystack, string needle) {const int n=haystack.size(),m=needle.size();vector<int>next(m+1,0);get_next(needle,next);for(int i=0,j=0;i<n;i++){while(j&&haystack[i]!=needle[j])j=next[j];if(haystack[i]==needle[j])j++;if(j==m)return i-m+1;}return -1;}
};
(如果你充分理解了本文,就会发现代码竟然如此直观) 。