串模式匹配-KMP算法详解

在我之前看过的数据结构书里，貌似对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...

ACXXACYYACA...

ACXXACYYACC...

XX/YY表示中间有任意长度的任意字符。上面可以看到显示出来的串最后一位是不同的，接下来我们看一下如果我们去找中间的重复串，将中间的那个AC滑动道后缀位置开始比较，

在第n次匹配时有如下结果：

ACXXACYYACA...
    ACXXACYYACC...
          ^
          j

若此时两串在j处匹配成功，那么Y=A并且X=Y=A。

那么明显不对了，这样最长的公共重复串就不是AC了。而是ACA....了，我们再次回过头让主串、模式串都重头开始匹配，

ACXXACYYACA...

ACXXACYYACC...

很明显，由于最后一位不匹配，A!=C，压根就不存在ACA的最长公共重复串。所以我们得出一个结论：跳过中间的重复串不会影响最终结果，而且不能找中间的重复串，必须找前缀。

好了，两大问题都解决了。现在回到刚开始那个问题，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还没更新完，还好我还没忘记。