「字符串」前缀函数|KMP匹配：规范化next数组 / LeetCode 28（C++）

概述

为什么大家总觉得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;}
};

（如果你充分理解了本文，就会发现代码竟然如此直观） 。