KMP算法计算next数组匹配字符串

朴灿烈づ我的快乐病毒、 2022-06-15 02:48 188阅读 0赞

## 1.概念 ##

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

设主串（ 称作S）为： ssasdsaaasdfsababaaabaasedfcv 模式串（ 称作T）为： ababaaaba用暴力算法匹配字符串过程中，我们会把S\[0\] 跟 T\[0\] 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时我们会丢弃前面的匹配信息，然后把T\[1\] 跟 W\[0\]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，极大地降低了匹配效率。而在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。

KMP算法的核心是 减少不比要的回溯，问题由模式串决定，不是有主串决定。

NEXT数组：当模式匹配串失败时，NEXT数组的元素指导 应该用T串的那个元素 进行下一轮的匹配。

不多说，代码加注释很详细，以免忘记。

## 2.代码 ##

//KMP Algorithm to find the Next Array and  begining index of matched position
    
    #include <stdio.h>
    #include <string.h>
    
    typedef char* String ;
    
    //获取 模式字符串T 的 next数组
    void get_next(String T, int *next)
    {
    	int j = 0;                //前缀索引
    	int i = 1;                //后缀索引
    	next[1] = 0;              //next数组第一个元素都为0
    	while (i < T[0])          //一直索引到模式字符串T最后一个元素
    	{
    		//待判断位置的 的 前缀元素与后缀元素若相同
    		if (0 == j || T[i] == T[j])
    		{
    			i++;              //后移一位 索引后缀元素  
    			j++;              //后移一位 索引前缀元素
    
    			//优化 ：加条件 if (T[i] != T[j])...
    			//待判断位置的后一位置 的 前缀元素与后缀元素若不相同，不需要回溯，直接确定next元素值
    			//实现功能：当子串中有“连续相同字符”失配(与主串不同)时，
    			//         直接从这一“连续相同字符”中的第一个字符 进行下一轮对比
    			if (T[i] != T[j])
    			{
    				next[i] = j;  //将j作为next数组对应元素		
    			}
    			//待判断位置的后一位置 的 前缀元素与后缀元素若相同，通过next数组向前回溯
    			else
    			{
    				next[i] = next[j];
    			}
    		}
    		// 待判断位置的 的 前缀元素与后缀元素若不相同
    		else
    		{
    			j = next[j];      //用next数组 j位置的当前元素 赋值给j,实现向前索引
    		}
    	}
    }
    
    //返回子串T在主串S第pos个字符之后的位置
    //若不存在，则返回为0
    int Index_KMP(String S, String T, int pos)
    {
    	int i = pos;
    	int j = 1;
    	int next[255];
    	get_next(T, next);
    
    	while (i <= S[0] && j <= T[0]) //当未索引到主串S及子串T最后一个位置时
    	{
    		if (0 == j || S[i] == T[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			j = next[j];       //子串元素与主串元素不相等时，通过next数组回溯
    		}
    	}
    	if (j > T[0])              //当索引子串T最后一个位置时,
    	{
    		return i - T[0];       //返回主串中与子串第一个元素相同的位置
    	}
    	else
    	{
    		return 0;
    	}
    }
    int main()
    {
    	
    	char strS[255] = " ssasdsaaasdfsababaaabaasedfcv";  //30
    	char strT[255] = " ababaaaba";      //10
    	strS[0] = 30;
    	strT[0] = 9;
    	int next[255];
    	int i = 1;
    	
    	//printf("主串strS为：\n %s \n", strS);
    	//printf("子串strT为：\n %s \n", strT);
    	
    	printf("主串strS为：\n");
    	for (i = 1; i < 30; i++)
    	{
    		printf("%c ", strS[i]);
    	}
    	printf("\n子串strT为：\n ");
    	for (i = 1; i < 10; i++)
    	{
    		printf("%c ", strT[i]);
    	}
    
    	get_next(strT, next);
    	printf("\n子串strT的next数组为： \n ");
    	for (i = 1; i < 10; i++)
    	{
    		printf("%d ", next[i]);
    	}
    
    	printf("\n匹配位置： \n " );
    	printf("%d ", Index_KMP(strS, strT, 0));
    	return 0;
    }

## 3.结果 ##

![Center][] ![Center 1][]

[Center]: https://img-blog.csdn.net/20170521234509320?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc2h5amh5cDEx/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220615/9847a6fea75948779365bcfa22617057.png