导语：数据结构基础-串模式匹配算法KMP

改进的模式匹配算法（KMP）：

改进之处在于，当匹配过程中出现相比较的字符不相等时，不需要回退主串的字符位置指针，而是利用已经得到的“部分匹配”的字符，将模式串向右滑动尽可能远的距离，再进行比较。具体向右滑动多少距离，就得依据next函数值进行计算。依据模式串next函数值整理的表，就叫《部分匹配表》。

滑动距离=已“部分匹配”的字符数-next函数值。

部分匹配表如何产生：

1.第一种方式：

“前缀”：除了最后一个字符外，一个字符串的全部头部组合。

“后缀”：除了第一个字符外，一个字符串的全部尾部组合。

“部分匹配值“：指前缀和后缀的最长共有元素的长度。也就是next函数值。

部分匹配表，就是根据部分匹配值（next函数值）整理得出。

如果模式串为abababb，则部分匹配表如下所示：

部分匹配表

我们定义下标0为字符串的开始，规定next[0]=-1;

j=1时，前面字符串a，前缀和后缀都为空集，共有元素最长长度为0；

j=2时，前面字符串ab，前缀为【a】,后缀为【b】,没有共有元素，共有元素最长长度为0;

j=3时，前面字符串aba，前缀为【a】【ab】,后缀为【a】【ba】,共有元素最长长度为1;

j=4时，前面字符串abab，前缀为【a】【ab】【aba】,后缀为【b】【ab】【bab】,共有元素最长长度为2;

j=5时，前面字符串ababa，前缀为【a】【ab】【aba】【abab】,后缀为【a】【ba】【aba】【baba】,共有元素最长长度为3;

j=6时，前面字符串ababab，前缀为【a】【ab】【aba】【abab】【ababa】,后缀为【b】【ab】【bab】【abab】【babab】,共有元素最长长度为4;

2.第二种方式

next函数定义如下：

next函数

如果模式串为abababb，根据next函数：

当j=0时，next[0]=-1。

当j=1时，因0<k<J,所以k不存在，不符合条件，因此next[1]=0。

当j=2时，0<k<2，则k=1。且p0=p1即a=b,不符合条件，因此next[2]=0。

当j=3时，0<k<3，则k=1，k=2。k=2时，且p0p1=p1p2即ab=ba,不符合条件，k=1时，且p0=p2即a=a,符合条件；因此next[3]=k=1。

当j=4时，0<k<4，则k=1，k=2,k=3。当k=3时，且p0p2=p1p3即aa==bb,不符合;k=2时，且p0p1=p2p3即ab=ab,符合条件；因此next[4]=k=2。

当j=5时，0<k<5，则k=1，k=2,k=3，k=4。k=4时，p0p3=p1p4即ab=ba,不符合条件; k=3时，p0p2=p2p4即aa=aa,符合条件；因此next[5]=k=3。

依次计算，就可以得到如图部分匹配表中的结果。

next函数推导过程如下：

我们定义串中的位置指针分别为i（主串指针）和j（模式串指针）,第一个位置以下标0开始，如下图所示：

根据KMP基本思想，当匹配到C和B不相等时，指针需要移动一定的距离，通过看上图我们发现，j需要移动到第二个位置，即C处，如下图所示的位置：

我们设匹配失败时，j要移动的下一个位置为k,此时k移动的位置只能在0到k之间，即0<k<J，如下图所示：

定义主串字符组为T,模式串字符组为P。

如上图所示，此时我们发现0<k<j时，P[0 ~ k-1]==P[j-k ~ j-1],即AB=AB。

整体总结如下：

当T[i] != P[j]时

由T[i-j ~ i-1] = P[0~j-1]

由P[0 ~ k-1] == P[j-k ~ j-1]

必然：T[i-k ~ i-1] == P[0 ~ k-1]

next函数值算法脚本

next函数

本文内容由小薇整理编辑！