KMP算法笔记

KMP算法原理

Next数组

Next数组在KMP算法中也叫做最长前缀后缀表，通过特定方法生成。

对于需要KMP匹配的模式串，构造next数组需要以下方法：

例如字符串 abcabdcaba

对于人工分析，我们进行如下拆分前缀和后缀

人工分析

我们发现对于一个模式串前缀和后缀存在相同字符串的中 相同字符串中的字符对个数 就为该段字符串对应的最长公共前后缀的长度，一个一个拆分字符是模拟计算机中一个一个遍历。

计算机角度分析

上一部分是对于人眼最直观的认识，那么计算机中怎么去求出这个Next数组呢？

我们首先来模拟程序中遍历字符串的过程

可以看见，指针在往右移动的过程中，指针走过的区域是不是就和上面所说的区域对应起来了？

aababc······

但这只是指针所走过的区域，说到底指针指向的只有一个字符，前面的字符过了就过了，怎么样才能从指针的遍历过程中来确定每一段前后缀的最长公共前后缀呢？

首先，对于模式串的第一个前缀位置，也就是当指针指向第一个字符的时候，该位置只有一个字符``，所以肯定为0。

对于第二个前缀ab ，根据目前的情况我们可以用当前指针加上偏移量来进行对比，如果不相同则该前缀对应的最长公共前后缀也为0。

但是对于第三种情况就出现问题了abc 我们需要对比a 和 c ，以及ab 和 bc，这样用偏移就会很麻烦，哪怕用双指针也很麻烦。

那么我们根据已知信息能不能方便后面的计算呢？

进一步分析：

在abc前缀的前面，我们已经计算了ab的最长公共前缀为0,这意味着前面两个字符不同,那么对于三个字符的前缀，最长公共前后缀已不可能为2。那么我们需要参考最长公共前后缀为1的情况进行对比。也就是从最短的前缀和后缀进行对比，对比a和c发现对不上，则该位置也为0。

那么我们来看看下面几种情况

abca 已知前面abc前缀的最长公共前后缀依然是0，那么退而求其次，对比最短前缀然后递增

为了每次我们对比前缀和后缀，那么需要两个指针x , y

对比a 和 a 发现相等，之前已知abc中没有相等的前后缀，$x!=y$ 所以 $xa!=ya$。该位置填1。

abcab 已知前面abca的最长公共前后缀为1，意味着abca中只有第一个前缀和第一个后缀相等，那么对于字符串abcab我们只需同时位移指针，对比第二个前缀b和最新的第一个前缀b，发现相等，所以在上一个前缀的最长公共前缀表的基础上加1，填入该位置，也就是2。

abcabd 已知前面abcab的最长公共前后缀为2，那么依照上一种情况的方法，我们需要往后对比c和d是否相等，如果不等则直接把之前记录的上一个前缀的最长公共前后缀填入。至于对比方法，我们知道在上一次进行对比abcab的时候我们得到了最长公共前后缀为2的答案，而在计算机中数组是以0开始的，我们可以之间将前缀指针定位到上一个最长公共前后缀的位置，指向的其实就是下一个成员c。

Next数组代码实现部分

首先我们需要两个指针来对比前后缀。

届时代码可以写成这样:

void buildNext(string& p, int* Next, int n) { int x,y; // x指针指向前缀，y指向后缀 }

而我们知道，对于公共前后缀是始终为 0 的，同时我们要保证前后缀指针之间是有间距的，否者进行位移的过程中它们始终会指向同一个位置。

于是得出了这样的代码：

void buildNext(string& p, int* Next, int n) { int x,y; // x指针指向前缀，y指向后缀 x = -1; y = 0; while(y < n) // n 为Next数组长度 { if(x == -1 || p[x] == p[y]) { Next[++y] = ++x; // x共用 } } }

$x=-1$的情况下j为0，满足条件后刚好会把Next的第一个元素赋为0，至于为什么是第一个，后面再介绍。

而后当x已经脱离第一次状态后，我们每次位移检查p[x] 和 p[y] 是否相等。但是目前的情况我们始终是在检查间距相同的两个成员，如果它们出现不等，就会得到错误的结果。

为此我们需要用到之前提到的，根据前面已知的最长公共前后缀的长度来进行对比，我们之间将前缀指针跳转到上一个字符串记录的最大公共前后缀的位置再进行比对，如此反复：

void buildNext(string& p, int* Next, int n) { int x,y; // x指针指向前缀，y指向后缀 x = -1; y = 0; while(y < n) // n 为Next数组长度 { if(x == -1 || p[x] == p[y]) { Next[++y] = ++x; // x共用 } else { x = Next[x]; } } }

在该程序中我们发现，x代表的其实是已匹配前缀的数量，同时也是未匹配前缀成员的地址。

当循环结束，就生成了一个Next数组。

KMP算法

原理

KMP算法我们会有一个原字符串和一个模式串，模式串依靠生成的Next数组在原字符串中进行查找。

next数组的目的是确定模式串中字符匹配失败向后位移的偏移量。

一般暴力匹配法：

暴力匹配算法会逐个匹配字符，如果匹配失败则会整体往后移动一位。这样如果有很多相同的字符，会做很多无用功。

KMP算法也是逐个匹配字符，但是当匹配失败时，可以根据Next中的前缀表确定往后移动的位置。跳过那些已经匹配过的字符。

在进一步说明之前，这里需要解释一下Next数组中为什么会从1开始存取最大公共前后缀。

试想一下，我们每一次匹配失败都会查前面前缀的表，那么如果是第一个前缀匹配失败，next中就没有明确的指示，那么一般我们会在next第0个成员写上-1，匹配失败则位移一位即可,而原Next数组的最后一个位置，已经没有数可以参考它，所以其实是可以丢弃的。

那么我们最终对应的效果如图：

结合上述所说，我们要在模式串第0个成员匹配失败后只位移一位，该模式串对应的之前的最大前缀数为-1，

那么我们要怎么让它往右位移一位呢？

根据下标，我们可以理解为把当前模式串中成员对应前缀表中的数再拿到模式串中来，然后把模式串中-1的位置移动到当前位置。如下图：

具体代码实现

int KMP(string t, string p) { int i = 0; // 主串位置 int j = 0; // 模式串位置 const int len = p.size() + 1; int next[len] = { -1 }; buildNext(p,next,p.size()); int tsize = t.size(); int psize = p.size(); // while 中的匹配方法是核心，前缀表生成和KMP本体匹配都用这个 while(i < tsize && j < psize) { if(j == -1 || t[i] == p[j]) { /* j = -1 时（next数组-1），直接匹配下一个位置。模式串index和next数组共用 */ i++; j++; } else { j = next[j]; // 如果匹配不上，则参照next数组表进行位移 } } if( j == psize) return i - j; else return -1; }

我们着重看后半部分

while(i < tsize && j < psize) { if(j == -1 || t[i] == p[j]) { /* j = -1 时（next数组-1），直接匹配下一个位置。模式串index和next数组共用 */ i++; j++; } else { j = next[j]; // 如果匹配不上，则参照next数组表进行位移 } } if( j == psize) return i - j; else return -1;

在while中，循环的条件是原字符串和模式串都没被遍历完，实际上未完成匹配时模式串是不会被遍历完的，所以要么遍历完整个原字符串，要么匹配成功就成功返回。

所以原字符串并不是一定遍历完全的，循环可能会在中途结束，所以i就相对而言成为了最终字符串的最后一个成员，而i到j的这段位置刚好就是字符串的位置，用i减去j就得到了中间这段字符串的开头位置。

再来分析循环内部的遍历部分：

while(i < tsize && j < psize) { if(j == -1 || t[i] == p[j]) { /* j = -1 时（next数组-1），直接匹配下一个位置。模式串index和next数组共用 */ i++; j++; } else { j = next[j]; // 如果匹配不上，则参照next数组表进行位移 } }

在循环中，我们从第0个字符串开始比较，如果比较到不同的字符，将p[j]对应的next[j]中指向的位置赋给j,相当于给指针做了一个重定向，也就是上面所说的把那个位置移动到当前位置了。字符串本身并不能随意的移动位置，所以我们只能通过切换指针来实现字符串的右移。把指定位置移动到当前位置，和把指向当前位置的指针定位指向指定位置的指针是等效的。

而如果是第一个成员匹配失败或者一直匹配成功则前后缀指针都往后移动然后进行下一轮比较。

去我的博客查看 ： Rudens博客