KMP 算法实现及next数组求解方法

野性酷女 2022-05-21 11:09 190阅读 0赞

KMP 中next数组求解方法

参考书：数据结构C语言版（第二版）

转载：[https://blog.csdn.net/wenyun\_kang/article/details/65436838?locationNum=13&fps=1][https_blog.csdn.net_wenyun_kang_article_details_65436838_locationNum_13_fps_1]

转载：[https://blog.csdn.net/iamyvette/article/details/77433991][https_blog.csdn.net_iamyvette_article_details_77433991]

一、文字描述求解法

现有字符串数组P\[n\],数组next\[n\]。（下标从1开始）

（1）      第1个字母的next置0（next\[1\]  = 0），第2个字母的next置1（next\[2\]  = 1）;

（2）      从第3个字母开始，计算第i个位置的next值时

判断 p\[i-1\] == p\[next\[i-1\]\]?  （i位置前一位的字母 和 i位置前一位的next值对应的字母是否相同）

若相等，则next\[i\]  = next\[i-1\] + 1;

若不等，则继续往回找，检查

p\[i - 1\] == p\[next\[next\[i-1\]\]\] ? （i位置前一位的字母 和 i位置前一位的next值作为next的下标所对应的字母 是否相同）

若相等，next\[i\]  = next\[next\[i-1\]\] + 1;

若不等，则继续往回找，直到找到下标为1还不相等，则next\[i\] = 1;

二、实例

（1）初始化

（3）      判断i = 3

第3位i的前一位(p\[i-1\])为第2位的b，b的next值为1对应内容为a，b与a不同，向前继续寻找next值对应的内容来与i的前一位(p\[i-1\])进行比较。因为找到第一位都没有找到与前一位相等的内容，所以第三位a的next值为1，则：

（4）      判断i = 4

第4位i的前一位为第3位的a，a的next值为1对应p\[1\]内容为a，相同，所以next\[i\]= 第3位的next值 + 1;  即为2

（5）  判断i = 5

第5位的a的前一位b的next值2对应内容为b，相等，所以该位a的next值就是前一位b的next值加上1，即为3

（5）判断i = 6

第6位的前一位a的next值3对应内容为a，相等，所以该位a的next值就是前一位a的next值加上1，即为4

（6）  判断i = 7

第7位的前一位a的next值4对应内容为b，不相等，向前继续寻找next值对应的内容来与前一位进行比较，b的next值2对应的内容为b，依旧不相等，继续向前寻找，第二位b的next值1对应内容为a，相等。因为是在第二位b处实现的相等，所以第七位a的next值为第二位b的next值上加1，即为2

（7）  判断i = 8

同样道理，得出b的next值为2

（8）  判断i = 9

第9位的前一位b的next值2对应内容为b，相等，所以此处next值为3

（9）  判断i = 10

同理next\[i\]为4

（10）  判断i = 11

第11位的前一位b的next值4对应内容为b，相等，所以此处next值为5

（11）  判断i = 12

第十二位同理可以得到next值位6

三、算法实例

#include <stdio.h>
 #include <string.h>
 
 
 #define MAXLEN 255
 
 
 //测试数组结构体 
 typedef struct Str{
 	char ch[MAXLEN + 1];
 	int length;
 	
 	Str(const char *chStr)//初始化 
 	{
 		strcpy(&ch[1],chStr); //因为数组从1开始 
 		length = strlen(&ch[1]) ;	
 	}
 
 
 }SString;
 
 
 //获得next数组 
 void get_next(SString T,int next[])
 {
 	int i =1;
 	int j =0;
 	next[1] = 0;
 	
 	while(i < T.length)
 	{
 		if((j == 0) || T.ch[i] == T.ch[j])
 		{
 			++j;
 			++i;
 			next[i] = j;
 		}
 		else
 		{
 			j = next[j];
 		}
 	}
 	
 }
 
 
 //KMP算法实现
 int Index_KMP(SString S,SString T,int pos,int next[])
 {
 	int i = pos; //T从S的pos位置之后开始匹配 1<= pos <= S.length 
 	int j = 1;  
 		
 	while(i <= S.length && j<= T.length)
 	{
 		if((j == 0) || S.ch[i] == T.ch[j])
 		{
 			++i;
 			++j;
 		}	
 		else
 			j = next[j];
 	} 
 	
 	if(j > T.length) 
 		return i-T.length; //匹配成功 返回匹配起始位置 
 	else
 		return -1;  //匹配失败 
 }
 
 
 
 
  
 int main()
 {
 	SString test1("ababaaababaa");
 	SString test2("aaab");
 	int next[test2.length];
 	int i=0;
 	int loc=0;
 	int pos = 1;
 	
 	//获取next[] 
 	get_next(test2,next);
 	printf("next[]=");
 	for(i = 1;i<=test2.length;i++)
 	{
 		printf("%d ",next[i]);
 	}
 	printf("\n");
 	
 	//KMP算法
 	loc = Index_KMP(test1,test2,pos,next);
 	printf("原串:%s\n",&test1.ch[1]);
 	printf("测串:%s\n",&test2.ch[1]);
 	printf("匹配起始位置:%d\n",loc);
 	
     return 0;
 }

四、补充

前缀后缀的最大公共元素长度

*  前缀：从第一个字母（必包括）开始往后看到最后一 个字母（不包括）为止的字符串的以第一个字母开头的子串   
    （比如“abab”的前缀有a,ab,aba）;
 *  后缀：简单来说，也就是，从最后一个字母（必包括）开始往前看到第一个字母（不包括）为止的字符串的子串   
    （比如“abab”的后缀有b,ab,bab）;
 *  最大公共子串长度：也就是前缀和后缀拥有的相同子串的最大长度   
    以“abab”为例：

<table style="border-spacing:0px;text-align:center;color:rgb(51,51,51);font-family:'-apple-system', 'SF UI Text', Arial, 'PingFang SC', 'Hiragino Sans GB', 'Microsoft YaHei', 'WenQuanYi Micro Hei', sans-serif, SimHei, SimSun;font-size:14px;background-color:rgb(255,255,255);"> 
 <thead> 
 <tr> 
 <th align="center" style="vertical-align:middle;">模式串的各个子串</th> 
 <th align="center" style="vertical-align:middle;">前缀</th> 
 <th align="center" style="vertical-align:middle;">后缀</th> 
 <th align="center" style="vertical-align:middle;">最大公共元素长度</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center" style="vertical-align:middle;">a</td> 
 <td align="center" style="vertical-align:middle;">空</td> 
 <td align="center" style="vertical-align:middle;">空</td> 
 <td align="center" style="vertical-align:middle;">0</td> 
 </tr> 
 <tr> 
 <td align="center" style="vertical-align:middle;">ab</td> 
 <td align="center" style="vertical-align:middle;">a</td> 
 <td align="center" style="vertical-align:middle;">b</td> 
 <td align="center" style="vertical-align:middle;">0</td> 
 </tr> 
 <tr> 
 <td align="center" style="vertical-align:middle;">aba</td> 
 <td align="center" style="vertical-align:middle;">a,ab</td> 
 <td align="center" style="vertical-align:middle;">a,ba</td> 
 <td align="center" style="vertical-align:middle;">1</td> 
 </tr> 
 <tr> 
 <td align="center" style="vertical-align:middle;">abab</td> 
 <td align="center" style="vertical-align:middle;">a,ab,aba</td> 
 <td align="center" style="vertical-align:middle;">b,ab,bab</td> 
 <td align="center" style="vertical-align:middle;">2</td> 
 </tr> 
 </tbody> 
</table>

[https_blog.csdn.net_wenyun_kang_article_details_65436838_locationNum_13_fps_1]: https://blog.csdn.net/wenyun_kang/article/details/65436838?locationNum=13&fps=1
[https_blog.csdn.net_iamyvette_article_details_77433991]: https://blog.csdn.net/iamyvette/article/details/77433991