KMP算法及其改进算法（随笔）

偏执的太偏执、 2022-11-25 00:51 139阅读 0赞

字符储存在1~length的位置上

### 简单模式匹配 ###

思路：从主串的第一个位置起和模式串的第一个字符开始比较，如果相等，则继续逐一比较后续字符；否则从主串的第二个字符开始，再重新用上一步的方法与模式串中的字符做比较，以此类推，直到比较完模式串中的所有字符。若匹配成功，则返回模式串在主串中的位置；若匹配不成功，则返回一个可区别于主串所有位置的标记，如“0”。

int index(Str str,Str substr)
    {
        
        int i = 1,j = 1,k = 1;//串从数组下标1位置开始存储，初值为1
        while(i <= str.length && j <= substr.length)
        {
        
            if(str.ch[i] == substr[j])
            {
        
                i++；
                j++;
            }
            else
            {
        
                j = 1;
                i = ++k;//匹配失败，i从主串的下一个位置开始匹配，k储存了主串上一次的起始位置
            }
        }
        if(j > substr.length)
            return k;
        else ruturn 0;
    }

主串（ABABCABCACBAB)和模式串(ABCAC)匹配过程

![35168072613f5a971dc070344fe75328.png][]

### KMP算法 ###

设主串为s1s2…sn,模式串为p1p2…pm，在上面的匹配过程中，经常出现一个关键状态（表2），其中i和j分别为主串和模式串中当前参与比较的两个字符的下标。

![101ed3a6e2a955e4be4b46a3fdce7f38.png][]

模式串的前部某子串P1P2…Pj-1与主串中的一个子串Si-j+1Si-j+2…Si-1匹配，而Pj与Si不匹配。每当出现这种状态时，简单模式匹配算法的做法是:一律将i赋值为i-j+2，j赋值为1，重新开始比较。这个过程反映到表2中可以形象地表示为模式串先向后移动一个位置，然后从第一个字符P1开始逐个和当前主串中对应的字符做比较；当再次发现不匹配时，重复上述过程。这样做的目的是试图消除Si处的不匹配，进而开始Si+1及其以后字符的比较，使得整个过程得以推进下去。

如果在模式串后移的过程中又出现了其前部某子串P1P2…与主串中某子串…Si-2Si-1相匹配的状态，则认为这是一个进步的状态。因为通过模式串后移排除了一些不可能匹配的状态，来到了一个新的局部匹配状态，并且此时Si有了和模式串中对应字符匹配的可能性。为了方便表述，记表中描述的状态为Sk，此处的新状态为Sk+1，此时可以将简单模式匹配过程看成一个由Sk向Sk+1推进的过程。当由Sk来到Sk+1时有两种情况可能发生:其一，S处的不匹配被解决，从si+1继续往下比较，若来到新的不匹配字符位置，则模式串后移寻找状态Sk+2；其二，Si处的不匹配仍然存在，则模式串继续后移寻找状态Sk+2如此进行下去，直到得到最终结果。

**说明:为了使上边其一与其二的表述看起来清晰工整且抓住重点，此处省略了对匹配成功与失败这两种容易理解的情况的描述。**

**说明:模式串后移使P1移动到Si+1，即模式串整个移过Si的情况也认为是Si处的不匹配被解决。试想，如果在匹配过程中可以省略掉模式串逐渐后移的过程，而从Sk直接跳到Sk+1，则可以大大提高匹配效率。带着这个想法，我们把Sk+1状态添加到表2中得到表3。**

![68d94ffb4a2e96594d2cad669e3e8659.png][]

观察发现，P1P2…Pj-1和Si-j+1Si-j+2…Si-1是完全相同的，且我们研究的是从Sk跳到Sk+1，因此，删除表3关于主串的一行，得到表4。

![562d7d610fd7cfecfac6516b94cf66dd.png][]

由表4可知，P1P2…Pt-1和Pj-t+1Pj-t+2…Pj-1匹配。记P1P2…Pj-1为F，记P1P2…Pt-1为FL，记Pj-t+1Pj-t+2…Pj-1为FR。所以，只需将F后移到使得FL和FR重合的位置（上表有色部位），即可实现Sk直接跳到Sk+1。

总结一般情况：每当发生不匹配的时候，找出模式串当中的不匹配的那个字符Pj，取其之前的子串F=P1P2…Pj-1，将模式串后移，使**F最先发生前部（FL）与后部（FR）相重合**的位置（见表中有色区域所示），即为模式串应后移的目标位置。

为了使问题表述得更形象，采用了模式串后移这种分析方式。事实上，在计算机中模式串是不会移动的，因此需要把模式串后移转化为j的变化，模式串后移到某个位置可等效于j重新指向某位置。容易看出，j处发生不匹配时，**j重新指向的位置恰好是F串中前后相重合子串的长度+1（串F或F长度+1）**。通常我们定义一个next\[j\]数组，其中j取1~m，m为模式串长度，表示模式串中第j个字符发生不匹配时，应从next\[j\]处的字符开始重新与主串比较。  
**特殊情况:**  
1）模式串中的第一个字符与主串i位置不匹配，应从下一个位置和模式串第一个字符继续比较。反映在从si+1与p1开始比较。  
2）当串F中不存在前后重合的部分时（不可将F自身视为和自身重合），则从主串中发生不匹配的字符与模式串第一个字符开始比较，反映在表2中即从s1与p1开始比较。  
下边以下表中的模式串为例，介绍求数组next的方法。

![ac348432628af69ca67e0b8cd0b04a67.png][]

1）当j等于1时发生不匹配，属于特殊情况1），此时将next\[1\]赋值成0来表示这个特殊情况。  
2）当j等于2时发生不匹配，此时F为“A”，属于特殊情况2），即next\[2\]赋值为1。  
3）当j等于3时发生不匹配，此时F为“AB”，属于特殊情况2），即next\[3\]赋值为1。  
4）当j等于4时发生不匹配，此时F为“ABA”，前部子串A与后部子串A重合，长度为1，因此next\[4\]赋值为2（F或FR长度+1）。  
5）当j等于5时发生不匹配，此时F为“ABAB”，前部子串AB与后部子串AB重合，长度为2，因此next\[5\]赋值为3。  
6）当j等于6时发生不匹配，此时F为“ABABA”，前部子串ABA与后部子串ABA最先发生重合，长度为3，因此next\[6\]赋值为4。  
7）当j等于7时发生不匹配，此时F为“ABABAB”，前部子串ABAB与后部子串ABAB最先发生  
重合，长度为4，因此next\[7\]赋值为5。

**注意:6）和7）中出现了“最先"字眼，以7）为例，F向后移动，会发生两次前部与后部的重合，第一次是ABAB，第二次是AB，显然最先发生重合的是ABAB。之所以选择最先的ABAB，而不是第二次的AB，是因为模式串是不停后移的，选择AB则丢掉了一次解决不匹配的可能性，而选择ABAB，即使当前解决不了，则下一个状态就是AB，不会丢掉任何解决问题的可能。这里也解释了一些参考书中提到的取最长相等前后的原因，7）中的ABAB或AB在一些参考书中称为F的相等前后缀（即FL和FR为F的相等前后缀），ABAB是最长相等前后缀，并且很显然的是，越先发生重合的相等前后缀长度越长。**

next数组

![5dffd3c155654faf6d97b1e15209b997.png][]

上述方法为手工求next数组的方法。介绍一下适用于转换成代码的高效的求next数组的方法。

假设next\[j\]的值已知，则next\[j+1\]的求值可以分两种情况分析。

1）若Pj等于Pt，显然next\[j+1\]=t+1，因为t为当前F最长相等前后缀长度（t为FL和FR长度）。  
2）若Pj不等于Pt，将Pj-t+1Pj-t+2…Pj当作主串，P1P2…Pt当作子串，则\*\*\*又回到了由状态Sk找Sk+1的过程\*\*\*，所以只需将t赋值为next\[t\]，继续进行Pj与Pt的比较，如果满足1）则求得next\[j+1\]，不满足则重复t赋值为next\[t\]，并比较Pj与Pt的过程。如果在这个过程中t出现等于0的情况，则应将next\[j+1\]赋值为1，此处类似于上边讲到的特殊情况2）。  
**说明:Sk直接跳到Sk+1，也就是通常所说的简单模式匹配算法中i不需要回溯。**  
**注意:KMP算法中的i不需要回溯这里隐藏着一个考点。i不需要回溯意味着对于规模较大的外存中字符串的匹配操作可以分段进行，读入内存一部分进行匹配，完成之后即可写回外存确保在发生不匹配时不需要将之前写回外存的部分再次读入，减少了I/O操作，提高了效率，在回答KMP算法较之于简单模式匹配算法的优势时，不要忘掉这一点。**

算法如下

void getnext(Str substr,int next[])
    {
        
    	int i = 1,j = 0;//串从下标为1的位置开始存储，i初值为1
    	next[1] = 0;
    	while(i < substr.length)
        {
        
    		if(j == 0 || substr.ch[i] == sbustr[j])
            {
        
    			++i;
    			++j;
    			next[i] = j;
    		}
    		else
    			j = next[j]//理解这一点，回溯
    	}
    }

得到next数组后，将简单模式匹配算法稍作修改就可以由状态Sk直接跳到Sk+1的改进算法，这就是知名的KMP算法，代码如下：

int KMP(Str str,Str substr,int next[])
    {
        
    	int i = 1,j = 1;//串从数组下标1处开始
    	while(i <= str.length && j <= substr.length)
        {
        
    		if(j == 0 || str.ch[i] == substr.ch[j])
            {
        
    			++i;
    			++j;
    		}
    		else
    			j = next[j];
    	}
    	if(j > substr.length)
    		return i - substr.length;
    	else
    		return 0;
    }

### KMP算法的改进 ###

先看一种特殊情况，见表7。当j等于5，发生不匹配时，因next\[5\]=4，则需将j回溯到4进行比较；又因next\[4\]=3，则应将j回溯到3进行比较…由此可见，j需要依次在5、4、3、2、1的位置上进行比较，而模式串在1到5的位置上的字符完全相等，因此较为聪明的做法应该是在j等于5处发生不匹配时，直接跳过位置1到4的多余比较，这就是KMP算法改进的切入点。

![fa1af97d167d45e3fd4e37ac6db7c2c7.png][]

将上述过程推广到一般情况为：  
若Pj等于Pk1（k1=next\[j\]），则继续比较Pj与Pk2（k2=next\[next\[j\]\]），若仍相等则继续比较下去，直到Pj与Pkn不等（kn=next\[next\[…next\[j\]…\]\]，嵌套n个next）或kn等于0时，则next\[j\]重置为kn。一般保持next数组不变，而用名为 nextval的数组来保存更新后的next数组，即当Pj与Pkn不等时， nextval\[j\]赋值为kn。  
下面通过一个例题来看一下 nextval的推导过程。  
【例】求模 ABABAAB式串的next数组和 nextval数组。  
首先求出next数组，见表8。

![4b7cbcc17a45db46059bc6119f919dac.png][]

1）当j为1时，nextval\[1\]赋值为0，特殊情况标记。  
2）当j为2时，P2为B，Pk1（k1=next\[2\]，值为1）为A，两者不等，因此 nextval\[2\]赋值为1。  
3）当j为3时，P3为A，Pk1（k1=next\[3\]，值为1）为A，两者相等，因此应先判断k2是否为0，而k2等于next\[next\[3\]\]，值为0，所以 nextval\[3\]赋值为k2，值为0。  
**注意:步骤3）中P3与Pk1（k1=next\[3\]）比较相等后，按照之前的分析应先判断k2是否为0，再让P3继续与Pk2比较，注意到此时 nextval\[next\[3\]\]即 nextval\[1\]的值已经存在，故只需直接将 nextval\[3\]直接赋值为 nextval\[1\]即可，即 nextval\[3\]=nextval\[3\]=0。**  
**推广到一般情况为:当Pj等于Pk1（k1=next\[j\]）时，只需让 nextval\[j\]赋值为 nextval\[next\[j\]\]即可。原因有两点：**  
**① nextval数组是从下标1开始逐渐往后求得的，所以在求 nextval\[j\]时， nextval\[next\[j\]\]必已求得。**  
**② nextval\[next\[j\]\]为Pj与Pk2到Pkn比较结果的记录，因此无须再重复比较。**  
4）当j为4时，P4为B，Pk（k=next\[4\]）为B，两者相等，因此 nextval\[4\]赋值为 nextval\[next\[4\]\]值为1。

5）当j为5时，P5为A，Pk（k=next\[5\]）为A，两者相等，因此nextval\[5\]赋值为nextval\[next\[5\]\]，值为0。

6）当j为6时，P6为A，Pk（k=next\[6\]）为B，两者不等，因此nextval\[6\]赋值为next\[6\]，值为4。

7）当j为7时，P7为B，Pk（k=next\[7\]）为B，两者相等，因此nextval\[7\]赋值为nextval\[next\[7\]\]，值为1。

由此求得nextval数组见表9

![47ad9c08a6d987012841e7788a762649.png][]

总结求nextval的一般步骤：

1）当j等于1时，nextval\[j\]赋值为0，作特殊标记。

2）当Pj不等于Pk时（k=next\[j\]），nextval\[j\]赋值为k。

3）当Pj等于Pk时（k=next\[j\]），nextval\[j\]赋值为nextval\[k\]。

求next数组的函数getnext()的核心代码段：

if(j == 0 || substr.ch[i] == substr.ch[j])
    {
        
    	++i;
    	++j;
    	next[i] = j;//1
    }
    else
    	j = next[j];//2

在注释1处next\[i\]已求出，且next\[0…i-1\]皆已求出，则结合上边的总结，要求nextval，可以在1处添加以下代码

next[i] = j;//1：i处不匹配，应跳回j处
    if(substr.ch[i] != substr.ch[next[i]])
    	nextval[i] = next[i];
    else
    	nextval[i] = nextval[next[i]];

显然，在注释2处用next数组来回溯j的代码可以用已求得的nextval数组代替（注意，j往前跳，之前的nextval值已经求得），修改后的代码如下：

j = nextval[j];//2

通过以上的分析，可以将函数的getnext()中的next数组用nextval数组代替掉，最终得到求nextval的代码：

void getnextval(Str substr,int nextval[])
    {
        
    	int i = 1,j = 0;//串从数组下标1位置开始储存，因此初值为1
    	nextval[1] = 0;
    	while(i < substr.length)
        {
        
    		if(j == 0 || substr.ch[i] == substr.ch[j])
            {
        
    			++i;
    			++j;
    			if(substr.ch[i] != substr.ch[j])
    				nextval[i] = j;
    			else
    			 nextval[i] = nextval[j];
    		}
    		else
    			j = nextval[j];
    	}
    }

[35168072613f5a971dc070344fe75328.png]: /images/20221124/3da64dc57c344d6fbdd6da029f7d7a8b.png
[101ed3a6e2a955e4be4b46a3fdce7f38.png]: /images/20221124/d37d4f89c3384f7c87f50e985adbf1ee.png
[68d94ffb4a2e96594d2cad669e3e8659.png]: /images/20221124/e85284a771b945cf8ca1594608179eb3.png
[562d7d610fd7cfecfac6516b94cf66dd.png]: /images/20221124/4e6c1e4325ea49ebb2fd5b1e00f6873c.png
[ac348432628af69ca67e0b8cd0b04a67.png]: /images/20221124/aa8b7e4b11894d55b5023c6b45499c04.png
[5dffd3c155654faf6d97b1e15209b997.png]: /images/20221124/bd7da1b4498b4242a873a6f3d3dcc1c9.png
[fa1af97d167d45e3fd4e37ac6db7c2c7.png]: /images/20221124/da1b80c177c54305b240b745ee4b8554.png
[4b7cbcc17a45db46059bc6119f919dac.png]: /images/20221124/c7b4c6cc4970488e9c983ed7e9c3d0a6.png
[47ad9c08a6d987012841e7788a762649.png]: /images/20221124/18739c7b37db475f83e1cfc7dbb920ec.png