串的模式匹配算法：KMP算法

深藏阁楼爱情的钟 2022-04-24 10:58 258阅读 0赞

串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，在主串s中找到等于子串t的过程称为模式匹配，如果找到，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回-1。t也称为模式。

###### 串的模式匹配有两种算法： ######

*  简单的模式匹配算法
 *  KMP算法

简单的模式匹配算法：  
  算法思想：首先将s1与t1进行比较，若不同，就将s2与t1进行比较，…，直到si和t1相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当si与tj不同时，则s返回到本趟开始字符的下一个字符，即si-j+2，t返回到t1，继续开始下一趟的比较，重复上述过程。若t中的字符全部比完，则说明本趟匹配成功，本趟的起始位置是i-j+1或i-t\[0\]，否则，匹配失败。  
  该算法比较简单，算法代码这里就不再给出。  
KMP算法  
  算法思想：算法中引入一个next数组：  
 n e x t \[ j \] = \{ 0 , 当 j = 1 时 M a x 1 , 其 他 情 况 next\[j\]=\\left\\\{ \\begin\{aligned\} 0,当j = 1时 \\\\ Max \\\\ 1,其他情况 \\end\{aligned\} \\right. next\[j\]=⎩⎪⎨⎪⎧0,当j=1时Max1,其他情况  
  其中：Max的取值为：  
 M a x = \{ k ∣ 1 < k < j 且 ′ p 1 p 2 . . . p k − 1 = ′ ′ p j − k + 1 . . . p j − 1 ′ Max=\\left\\\{ \\begin\{aligned\} k|1<k<j且&\#x27;p\_1p\_2...p\_\{k-1\}=&\#x27;&\#x27;p\_\{j-k+1\}...p\_\{j-1\}&\#x27; \\end\{aligned\} \\right. Max=\{ k∣1<k<j且′p1p2...pk−1=′′pj−k\+1...pj−1′  
例如：  
![20190423115330521.png][]  
next\[j\]的计算过程如下：

*  j=1时，根据定义next\[1\]=0;
 *  j=2时，由于不存在这样的正整数k使得1<k<2，所以属于其他情况，此时next\[2\]=1;
 *  j=3时，1<k<3，此时k只能取2，比较p1与p2(即pj-k+1或者说是pj-1)，发现a!=b，所以属于其他情况，next\[3\]=1;
 *  j=4时，1<k<4，此时k可以取2、3两个：首先k取2，则比较p1与p3(即pj-k+1或者说是pj-1)，发现相等，说明k可以取2；然后计算k取3时的情况，需要判断p1p2与p2p3(即pj-k+1pj-1)，发现ab!=ba，k不可以取3；最后找出k的最大取值为2，所以next\[4\]=2
 *  j=5时，1<k<5，此时k可以取2、3、4三个 ：首先k取2，则比较p1与p4(即pj-k+1或者说是pj-1)，发现相等，说明k可以取2；然后计算k取3时的情况，需要判断p1p2与p3p4(即pj-k+1pj-1)，发现ab!=aa，k不可以取3；然后计算k取4时的情况，需要判断p1p2p3与p2p3p4(即pj-k+1pj-k+2pj-1)，发现aba!=baa，k不可以取4；最后找出k的最大取值为2，所以next\[5\]=2
 *  j=6时，1<k<6，此时k可以取2、3、4、5四个：首先k取2，则比较p1与p5，发现由于a!=b，说明k不可以取2；然后计算k取3时的情况，需要判断p1p2与p4p5，发现ab==ab，k可以取3；然后计算k取4时的情况，需要判断p1p2p3与p3p4p5，发现aba!=aab，k不可以取4；然后计算k取5时的情况，需要判断p1p2p3p4与p2p3p4p5，发现abaa!=baab，k不可以取5；最后找出k的最大取值为3，所以next\[6\]=3
 *  j=7时，同理照此方法取k=2、3、4、5、6进行比较，最后计算出没有一个k值满足，所以属于其他情况，因而next\[7\]=1
 *  j=8时，按照上述方式进行计算k=2、3、4、5、6、7比较后，发现只有k只能取2，因而next\[8\]=2。

从而得出next数组中的值

算法代码如下：

#include "stdafx.h"
    #include <stdio.h>
    
    //查找满足条件的最大的k值，tr为模式串，l为当前比较的位置
    int Max_k(char t[],int l)
    {
        
    	int i = 0;
    	int max = 0;
    	int k = 0;
    	bool bIsEqual = true;
    	for(k = 2;k < l;k++)
    	{
        
    		bIsEqual = true;
    		for(i = 1;i <k;i++)
    		{
        
    			if(t[i] != t[l-k+i])
    				bIsEqual = false;//不满足'p1p2...p(i-1)==p(l-k+1)...p(l-1)'条件
    		}
    		if(bIsEqual)
    			max = k;
    	}
    	return max;
    }
    //计算模式串的next[j]数组
    void NextArr(int next[],int t_len,char t[])
    {
        
    	next[1] = 0;//netx[1]=0
    	next[2] = 1;//1<k<i,此时i = 2，为其他情况，所以next[2] = 1
    	int i = 3;
    	int max = 0;
    	for(i = 3;i < t_len;i++)
    	{
        
    		max = Max_k(t,i);
    		if(0 == max)
    			next[i] = 1;//其他情况
    		else
    			next[i] = max;
    	}
    }
    //找到匹配的主串开始位置
    //s:主串，t:子串,s_len:主串长度,t_len:子串长度,pos:从主串的pos位置处开始查找,next:不匹配时j的重新定位位置
    int KMP_Pos(char s[],char t[],int s_len,int t_len,int pos,int next[])
    {
        
    	int i = pos;
    	int j = 1;
    	while(i < s_len && j < t_len)
    	{
        
    		if(j == 0 || s[i] == t[j])
    		{
        
    			i++;
    			j++;
    		}
    		else
    		{
        
    			j = next[j];
    		}
    	}
    	if(j >= t_len)
    		return i - t_len + 1;
    	else
    		return 0;
    }
    
    int main(int argc, char* argv[])
    {
        
    	char s[] = {
        '0','a','b','a','b','c','a','b','c','a','c','b','a','b'};//主串
    	int s_len = 14;
    	char t[] = {
        '0','a','b','c','a','c'};//模式串
    	int t_len = 6;
    	int next[6];
    	NextArr(next,t_len,t);
    	int pos = KMP_Pos(s,t,s_len,t_len,1,next);
    	printf("主串匹配模式串的第一个位置为：%d\n",pos);
    	return 0;
    }

运行结果为：  
![在这里插入图片描述][20190423120320309.png]  
  KMP算法的难点就在于计算next数组，当计算出模式串的next的数组后，再去进行模式串匹配算法就比较简单了。

[20190423115330521.png]: /images/20220216/898c0ee6a76b4cf49eb92f306c31746b.png
[20190423120320309.png]: /images/20220216/17fcdb1776e344afb639671da1b7fd6a.png