在我之前看过的数据结构书里，貌似对KMP总是一笔带过，给我感觉就好似没必要学一样。这次呢，好不容易呢，在严奶奶的数据结构C语言第二版书上提到KMP算法实现，结果老师认为这个太难了，觉得没必要学，也就没讲。这可不行啊，这已经激起了我的好奇心，我更是想把KMP搞懂了。
这几天花了点时间，研究了一下。有点心得，希望可以通过这次总结，来把这个算法的一些细节梳理清楚，也算是考验一下自己是否有真正理解这个算法。
KMP由来
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。
在KMP算法之前，在业内还有一个非常常用的简单匹配算法-BF算法。推荐大家先去看一下笔者BF算法的文章：串的模式匹配-BF算法
BF算法简单直观而且好用。不过他很“蠢”。蠢在哪里呢？因为它在发生不匹配的情况下，总是需要回溯主串的指针。如果字符串中重复的字符比较多，如主串“AAAAAAAAAAB”中查找“AAAB”，每次都需要回溯指针重头开始匹配，比较到最后一个才知道不匹配。这样该算法的执行效率就显得非常低了。三位大佬们是无法忍受“暴力破解”这种低效的手段的，于是他们三个Brute-Force算法的基础上同时提出的模式匹配的改进算法，研究出了不需要回溯主串指针的KMP算法，从而可以大大提高效率。
2022/10/24 14:00 先午睡一小会
KMP思想
当匹配过程中产生“失配”时，主串指针i不变，利用已经得到的“部分匹配”的结果，让模式串尽可能远的右滑一段距离，再继续比较。
所以如何记录“失配”时的“部分匹配”的结果，成了KMP的重点。
在KMP算法中，我们将这些部分匹配结果称为next数组。
Next数组
怎么解释呢？next数组到底是如何生成的？
我们为了在“失配”时能够右滑对应的位置，重新比较主串与模式串。于是引入了next数组。
我们假设模式串中的每个位置(字符)都可能发生“失配”情况，而next数组中就对应存放着当模式串第j个位置（假设指针j指向模式串的某个位置）与主串发生“失配”时，要右滑的目标位置。
那么就引出了下一个问题？目标位置如何确定？以及它到底指什么？有什么作用？
目标位置
目标位置是next数组的重点，前面说到kmp的重点是如何生成next数组，那目标位置也就是kmp的重中之重了。
所以目标位置是什么？这里笔者先暂且将目标位置称之为K，在生成next数组中需要用到J、K两个指针，在这里先不提K在next数组还有什么作用，随后慢慢展开。（先说明一点：这里笔者所说的指针并不是实际编程语言中的指针变量那个指针，也可以是一个用于记录索引位置的int变量）。
在笔者看来，K就是用来找最长公共前后缀。而且KMP算法中next数组也就是通过这个最长公共前后缀思想来生成的。所以我们也把next数组，叫做前缀表。至于为什么要找最长公共前后缀，我们来细细道来。
假设模式串为ABCABA....
什么是前后缀？
当模式串J位置发生不匹配时，J位置之前紧挨着的子串叫做后缀。我们要从模式串头位置开始寻找能与j位置前面这个后缀匹配上的子串，所以称这个从头开始的子串叫做前缀。但这么说就对了吗？我们看下面这种图，我们发现按照我们这样说，最后前后缀的结果是J前面的一个完整的一个子串，它们是共同(公共)的，但对我们来说没有意义。实际上我们对于前后缀的定义落了一个重要的条件，要有明确范围的。只有有了明确范围的，才能保证前后缀指的不是一份J前面那个完整的串，而是个有意义的串。
说明：在下面介绍前后缀篇幅中，暂且将指针J位置之前的ABCAB这个子串，直接称为子串。
于是我们对前后缀有了以下定义。
前后缀定义
前缀：包含模式串首个字符的但并不包含子串的最后一个字符的串。
后缀：包含子串的最后一个字符但并不包含模式串首个字符的串。
什么是最长公共前后缀？
在子串中找到最长的两串满足前后缀定义且两串相等，如下图所示。
我们知道了最长公共前后缀是什么了。但我们要知其所以然，现在再来说说为什么要确定最长公共前后缀。先说说为什么要确定后缀
为什么要确定后缀
我们自己想象一下，有没有发现指针j所指位置上的字符前面都是之前与主串已经成功匹配成功过的了（因为只有当前面的串都与主串匹配成功了，才能进行到这次的匹配判断），只要把模式串中一个重复串(一样的子串)移动过来，就可以跳过无用的匹配直接移动过来了。是不是想问什么意思？我们再来看下图。
前缀这个重复串移动到了原先后缀的位置上去了。因为我们知道后缀与主串是匹配的，那么只要在j之前的子串中找到一个与后缀相同的重复串再来跟主串进行匹配。而且我们在图中发现在右滑模式串的时候，主串的i指针并不发生改变。(这就是KMP的特点，无需回溯主串的指针，继续进行比较。)
一个问题解决，又带来一个问题。另一个重复串（与后缀一样的串）为什么一定要是前缀呢？如果中间也有重复串呢，为什么不用中间的？这样会不会跳过中间的能匹配成功的，导致结果错误呢？我们来证明一下，看一下跳过中间的串是否会有影响？
为什么一定要是前缀呢？
我们假设主串为：ACXXACYYACA... 模式串为ACXXACYYACC...
XX/YY表示中间有任意长度的任意字符。
在第n次匹配时有如下结果：
ACXXACYYACA...
ACXXACYYACC...
^
j若此时两串在j处匹配成功，则Y=A并且X=Y=A。
那么明显不对了，这样最长的公共前后缀就不是AC了。而是ACAAA……。所以我们得出一个结论：跳过中间的重复串不会影响最终结果，而且不能找中间的重复串，必须找前缀。
好了，两大问题都解决了。现在回到刚开始那个问题，K是如何找前后缀的？
2022/10/25 21:50 今天码这篇文章时间花的有点多，明天再来更新吧。
2022/10/27 1:18 边看电影边喝咖啡，现在有点睡不着了，码一会字再睡吧。
K是如何找前后缀的
这里我觉得是生成next数组最重要的一点，网上很多文章千篇一律，几乎都没有对这块详细展开，或许他们是落写了，也或许……嗯？你明白吧。
首先K既然是找前后缀的，必然还需要有一个指针要与之作匹配，这个指针就是前面所说的指针j，且位置必然不同，那么K一定在指针j的前面(指位置关系)，即有k<j。在指针j一直向后移动的同时，判断k所指字符是否与j所指字符匹配，若匹配，则j、k继续向后移动，并且在j的下一个位置，即j+1处 对应next数组中的j+1处记录K，next[j+1]=k+1。（这里公式中的j、k还未向后移动）
有人可能会疑问？为什么要向后移动，这个向后移动的目的是什么？那么这里我详细讲一下，不管你前面是否看懂了，请先接着看下去。之所以匹配成功后j、k还要向后移动是因为我们要找最长公共前后缀呀！不是吗？既然前面的字符匹配成功了，那说明一定存在k之前的子串与j之前，j-k之后的子串匹配，即t1t2····tk-1=tj-k+1 tj-k+2····tj-1 那当然我们的匹配过程要持续下去，直到我们确定了最长公共前后缀。
至于为何要在next[j+1]处记录k+1，其实很简单，在解释前让我们先看一张图。
为了更直观更清晰，我这里数组下标从1开始。（从0开始一个道理）
看这张图，我们知道前缀是从头开始的，那么k在这里不就是我们的最长公共前后缀的长度吗？之所以+1，是因为当j+1位置上的字符如果与主串“失配”时，我们应该要让此时的j+1的跳到我们的k+1的位置上，这就是我们所说的模式串右滑。所以最终我们可以得到，当j、k向后移动后，有next[j]=k。
那若是K左边再无子串呢？表明模式串无法右滑了，这时候k、j只需要向后移动，则j+1，k+1，同时next[j]=k;
现在next数组我们大概了解了是如何生成的了，我们可以试着手推一下next数组。
2022/10/27 2:17 有点困了，睡了。晚安，明天见！
思路已经清晰了，我们来写一下代码。
好，按照上面的思路，现在将思路先转换为代码来试试，我们假设数组起始索引为1。代码如下：
void getNextArr(char* ps,int next[],int length)
{
int j=1;//一直后移动
//k一定要比j小,因为要比较前后缀
int k=0;
next[1]=0;
while (j<length)
{
//k==0执行里面语句，因为说明k左边没有子串了，肯定不能右滑了，k要向后移动
//如果匹配要继续后移
if(k==0||ps[j]==ps[k])
{
++j;
++k;
//next[j+1]=k+1
next[j]=k;
}
else
{
//不匹配的话，要右滑。
//而且k左边还有字符，需要右滑
k=next[k];//next[k]一定比原来的k小，因为要右滑
}
}
}
int main()
{
char* p=" abcabac";//假设数组索引从1开始，那么字符串前加一个空白字符用来占位。
int strLength=strlen(p);
int* next=new int[strLength];//moreover->sizeof(next)/sizeof(next[0])
getNextArr(p,next,strLength);
for (int i = 0; i < strLength; i++)
{
cout<<next[i]<<endl;
}
system("pause");
return 0;
}假设串为abcabac，结果为：
-1163005939//数组索引为0的元素,因为上面代码中next数组数据从1开始生成，故此处为随机数
0
1
1
1
2
3
2
请按任意键继续. . .注意：上面这段代码，因为数组与串索引从1开始,数组索引为0的位置未赋值，所以输出的数组索引为0的元素为随机数。
现在看这段代码，是不是感觉很简单了。
我们知道，在c++中序列的起始索引是0开始的，我们算法中的串索引从0开始遍历更符合语言逻辑，上面的代码需要稍微修改一下，j初始值应该为0，则k初始值为-1，判断k左边有无子串时，只需判断k是否等于-1。
数组起始索引为0：
运行代码：
void getNextArr(char* ps,int next[],int length)
{
int j=0;//一直后移动
//k一定要比j小,因为要比较前后缀
int k=-1;
next[0]=-1;
while (j<length)
{
//k==0执行里面语句，因为说明k左边没有子串了，肯定不能右滑了，k要向后移动
//如果匹配要继续后移
if(k==-1||ps[j]==ps[k])
{
++j;
++k;
//next[j+1]=k+1
next[j]=k;
}
else
{
//不匹配的话，要右滑。
//而且k左边还有字符，需要右滑
k=next[k];//next[k]一定比原来的k小，因为要右滑
}
}
}
int main()
{
//note 以索引0为起始索引
char* p="abcabac";
int strLength=strlen(p);
int* next=new int[strLength];//moreover->sizeof(next)/sizeof(next[0])
getNextArr(p,next,strLength);
for (int i = 0; i < strLength; i++)
{
cout<<next[i]<<endl;
}
system("pause");
return 0;
}
输出结果：
-1
0
0
0
1
2
1因我们的起始索引改变了，指针之间差1，所以的输出结果也差1。其实没差，只要我们确定了序列起始索引，做相应的处理，那么这里不会影响最终的算法结果。
2022/11/3 11:50 才想起来KMP还没更新完，还好我还没忘记。
