数据结构——模式匹配kmp算法

淡淡的烟草味﹌ 2022-12-24 13:52 194阅读 0赞

暴力算法

//暴力算法
    int index(SString S,SString T,int pos)
    {
        
    	int i=pos,j=1;
    	while(i<=S[0]&&j<=T[0])
    	{
        
    		if(S[i]==T[j])
    			{
        
    				++i;
    			 ++j;
    			}
    		else 
    			{
        
    				i=i-j+2;
    				j=1;
    			
    			}
    	}
    	if(j>T[0])
    		return i-T[0];
    	 else return 0;
     }

kmp算法

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20201201114708286.gif_pic_center]

next\[\]数组的求法：  
例子：abaabcac  
![在这里插入图片描述][20201201115346443.png]  
模式串的下标从1开始

1.  第一位固定为0；
2.  第二位固定为1；
3.  从第三位（i）开始（其余的每一位都如此），  
    从该位 (i) 的前一位开始，从右向左寻找子串  
    从模式串的头部（最左边）,从左向右寻找子串  
    找到两头子串的最大相同的个数  
    把最大相同的个数的下一位的索引给next\[i\]

//next函数算法 
    void get_next(SString T,int next[])
    {
        
    	int j; 
    	int i=1;next[1]=0;j=0;
    	while(i<T[0])
    	{
        
    		if(j==0||T[i]==T[j]){
        i++;j++;next[i]=j;}
    		else j=next[j];
    		
    	}
    }
    int Index_KMP(SString S,SString T,int pos)
    {
        	
    
    	int next[MAXSTRLEN+1]; 
    	get_next(T,next);
    	int i=pos;  int j=1;
    	while(i<=S[0]&&j<=T[0])//i j都不超过其串的长度
    	 
    	{
        //失配 
    		//1：失配，当j==0时，则目标主串的检测指针前进一位，模式串检测指针回到T[1].进行下一趟的比较
    		
    		//2：失配，当j>0时，那么在下一趟比较时，模式串的起始位置为Tnext[j],目标主串S的检测指针不回溯，仍然指向上一趟失配的位置 
    		
    		if(j==0||S[i]==T[j])
    		{
        
    			++i;++j;//继续比较后继字符 
    		}
    		else j=next[j];//模式串向右移动 
    		
    		
    	}
    	
    	if(j>T[0]) return i-T[0];//匹配成功 
    	else return 0;
    }

kmp算法改进版  
例子：abaabcac

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]

求nextval\[\]数组：（需要根据next\[\]数组来求）  
1.

void get_nextval(SString T,int nextval[])
    {
        
    	int j; 
    	int i=1;nextval[1]=0;j=0;
    	while(i<T[0])
    	{
        
    		if(j==0||T[i]==T[j])
    		{
        i++;j++;
    		
    		if(T[i]!=T[j])
    			nextval[i]=j;
    		 
    		 else 
    		 	nextval[i]=nextval[j];
    		
    		}
    		else j=nextval[j];
    		
    	}
    }
    
    int Index_KMP_val(SString S,SString T,int pos)
    {
        	
    
    	int nextval[MAXSTRLEN+1]; 
    	get_nextval(T,nextval);
    	int i=pos;  int j=1;
    	while(i<=S[0]&&j<=T[0])//i j都不超过其串的长度
    	 
    	{
        //失配 
    		//1：失配，当j==0时，则目标主串的检测指针前进一位，模式串检测指针回到T[1].进行下一趟的比较
    		
    		//2：失配，当j>0时，那么在下一趟比较时，模式串的起始位置为Tnext[j],目标主串S的检测指针不回溯，仍然指向上一趟失配的位置 
    		
    		if(j==0||S[i]==T[j])
    		{
        
    			++i;++j;//继续比较后继字符 
    		}
    		else j=nextval[j];//模式串向右移动 
    		
    		
    	}
    	
    	if(j>T[0]) return i-T[0];//匹配成功 
    	else return 0;
    }

包含三个算法的全部程序代码

#include <stdio.h>  // printf(); scanf()
    #include <stdlib.h> // exit()
    #include <malloc.h> // malloc()
    #include <time.h>   // srand((unsigned)time(NULL));
    #include <string.h>
     
    // 函数结果状态代码
    #define TRUE    1
    #define FALSE   0
    #define OK      1
    #define ERROR   0
    #define INFEASIBLE  -1
    #define OVERFLOW    -2
    
    // Status是函数的类型，其值是函数结果状态代码
    typedef int Status;
     
    // #define ElemType int  // 也可以用宏定义确定ElemType类型
    typedef int ElemType;
    // Status是函数的类型，其值是函数结果状态代码
    
     -----串的定长顺序存储表示-----
    #define MAXSTRLEN 255                            // 用户可在255(1个字节)以内定义最大串长
    typedef unsigned char SString[MAXSTRLEN + 1];   // 0号单元存放串的长度
    
    
    Status StrAssign(SString &T, char *chars) {
        
    	if(strlen(chars) > MAXSTRLEN)
    		return ERROR;
    	else {
        
    		T[0] = strlen(chars);       // 0号单元存放串的长度
    		for(int i=1; i<=T[0]; i++)
    			T[i] = *(chars+i-1);
    		return OK;
    	}
    }
    
    
    Status StrCopy(SString &T, SString S) {
        
    	for(int i=0; i<=S[0]; i++)
    		T[i] = S[i];
    	return OK;
    }
    
    int StrCompare(SString S, SString T) {
        
    	int i;
    	for(i=1; i<=S[0] && i<=T[0]; ++i)
    		if(S[i] != T[i])
    			return S[i]-T[i];
    	return S[0]-T[0];
    }
    
    int StrLength(SString S) {
        
    	return S[0];
    }
    
    Status StrEmpty(SString S) {
        
    	if(S[0] == 0)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    Status Concat(SString T, SString S1, SString S2) {
        
    	// 若未截断，则返回TRUE；否则返回FALSE。
    	int i;
    	if(S1[0]+S2[0] <= MAXSTRLEN)   // 未截断
    			{
        for(i=1; i<=S1[0]; i++)     // 将串S1赋给T
    			T[i] = S1[i];
    			for(i=1; i<=S2[0]; i++)     // 将串S2赋给T中已有串S1的后面
    			T[S1[0]+i] = S2[i];
    			T[0] = S1[0] + S2[0];       // 新串的长度
    			return TRUE;
    			} 
    	else if(S1[0] < MAXSTRLEN) {
          // 截断S2的部分字符序列
    		for(i=1; i<=S1[0]; i++)     // 将串S1赋给T
    			T[i] = S1[i];
    		for(i=1; i<=MAXSTRLEN-S1[0]; i++)// 将串S2未截断的部分赋给T中已有串S1的后面
    			T[S1[0]+i] = S2[i];
    		T[0] = MAXSTRLEN;
    		return FALSE;
    	} else {
                                // 截断(仅取S1)
    		for(i=1; i<=MAXSTRLEN; i++) // 将串S1赋给T
    			T[i] = S1[i];
    		T[0] = MAXSTRLEN;
    		return FALSE;
    	}
    }//Concat 算法 4.2
    // 初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。
    // 操作结果：用Sub返回串S的第pos个字符起长度为len的子串。
    Status SubString(SString Sub, SString S, int pos, int len) {
        
    	int i;
    	if(pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
    		return ERROR;
    	for(i=1; i<=len; i++)
    		Sub[i] = S[pos+i-1];
    	Sub[0] = len;
    	return OK;
    }
    
    void StrPrint(SString T) {
        
    	for( int i = 1; i<= T[0]; i++)
    		printf("%c ", T[i]);
    	printf("\n");
    }
    //将模式串的next函数值存入到数组next中 
    //next函数算法 
    void get_next(SString T,int next[])
    {
        
    	int j; 
    	int i=1;next[1]=0;j=0;
    	while(i<T[0])
    	{
        
    		if(j==0||T[i]==T[j]){
        i++;j++;next[i]=j;}
    		else j=next[j];
    		
    	}
    }
    
    
    //利用模式串T的next函数求T在主串S中第pos个字符之后的位置
    //KMP算法 其中T非空  1<=pos<=StrLength(S) 
    
    void get_nextval(SString T,int nextval[])
    {
        
    	int j; 
    	int i=1;nextval[1]=0;j=0;
    	while(i<T[0])
    	{
        
    		if(j==0||T[i]==T[j])
    		{
        i++;j++;
    		
    		if(T[i]!=T[j])
    			nextval[i]=j;
    		 
    		 else 
    		 	nextval[i]=nextval[j];
    		
    		}
    		else j=nextval[j];
    		
    	}
    }
    
    
    int Index_KMP(SString S,SString T,int pos)
    {
        	
    
    	int next[MAXSTRLEN+1]; 
    	get_next(T,next);
    	int i=pos;  int j=1;
    	while(i<=S[0]&&j<=T[0])//i j都不超过其串的长度
    	 
    	{
        //失配 
    		//1：失配，当j==0时，则目标主串的检测指针前进一位，模式串检测指针回到T[1].进行下一趟的比较
    		
    		//2：失配，当j>0时，那么在下一趟比较时，模式串的起始位置为Tnext[j],目标主串S的检测指针不回溯，仍然指向上一趟失配的位置 
    		
    		if(j==0||S[i]==T[j])
    		{
        
    			++i;++j;//继续比较后继字符 
    		}
    		else j=next[j];//模式串向右移动 
    		
    		
    	}
    	
    	if(j>T[0]) return i-T[0];//匹配成功 
    	else return 0;
    }
    
    int Index_KMP_val(SString S,SString T,int pos)
    {
        	
    
    	int nextval[MAXSTRLEN+1]; 
    	get_nextval(T,nextval);
    	int i=pos;  int j=1;
    	while(i<=S[0]&&j<=T[0])//i j都不超过其串的长度
    	 
    	{
        //失配 
    		//1：失配，当j==0时，则目标主串的检测指针前进一位，模式串检测指针回到T[1].进行下一趟的比较
    		
    		//2：失配，当j>0时，那么在下一趟比较时，模式串的起始位置为Tnext[j],目标主串S的检测指针不回溯，仍然指向上一趟失配的位置 
    		
    		if(j==0||S[i]==T[j])
    		{
        
    			++i;++j;//继续比较后继字符 
    		}
    		else j=nextval[j];//模式串向右移动 
    		
    		
    	}
    	
    	if(j>T[0]) return i-T[0];//匹配成功 
    	else return 0;
    }
    
    //暴力算法
    int index(SString S,SString T,int pos)
    {
        
    	int i=pos,j=1;
    	while(i<=S[0]&&j<=T[0])
    	{
        
    		if(S[i]==T[j])
    			{
        
    				++i;
    			 ++j;
    			}
    		else 
    			{
        
    				i=i-j+2;
    				j=1;
    			
    			}
    	}
    	if(j>T[0])
    		return i-T[0];
    	 else return 0;
     } 
    
    int main()
    {
        	
    		int x;int number;int pos;
    	char  c[MAXSTRLEN+1],d[MAXSTRLEN+1];
    	SString S;
    	SString T;
    	printf("输入字符串S（主串）：");
    	scanf("%s",c);
    
    	if(!StrAssign(S, c)) {
        
    		printf("串长超过MAXSTRLEN=%d，程序正常退出。\n", MAXSTRLEN);
    		exit(0);}
    
    	printf("输入字符串T（模式串）：");
    	scanf("%s",c);
    
    	if(!StrAssign(T, c)) {
        
    		printf("串长超过MAXSTRLEN=%d，程序正常退出。\n", MAXSTRLEN);
    		exit(0);}	
    	//	StrPrint(S);
    	//	StrPrint(T);
    	
    	printf("输入要在主串开始的位置pos：");
    	scanf("%d",&pos);
    	
    	printf("选择要是用的算法1（暴力算法）/2（kmp算法next）/3（kmp算法nextval）:");
    	scanf("%d",&x);
    	 if(x==1)
    	 		{
        number=index(S, T, pos);
    			 printf("%d",number);}
    	 else if(x==2)
    	 {
        int next1[MAXSTRLEN+1];
    	get_next( T,next1);
    		for(int i=1;i<=T[0];i++)
    		{
        
    			printf("%d ",next1[i]);
    		}
    		printf("\n"); 
    	
    		number=Index_KMP(S,T,pos);
    		printf("%d",number);
    	 }
    	 
    	 else if(x==3)
    	 
    	  {
        int nextval1[MAXSTRLEN+1];
    	get_nextval( T,nextval1);
    		for(int i=1;i<=T[0];i++)
    		{
        
    			printf("%d ",nextval1[i]);
    		}
    		printf("\n"); 
    	
    		number=Index_KMP_val(S,T,pos);
    		printf("%d",number);
    	 }
    	 return 0;
    		
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221120/3d011d6d62494fccb15f51a28f5e505e.png
[20201201114708286.gif_pic_center]: https://img-blog.csdnimg.cn/20201201114708286.gif#pic_center
[20201201115346443.png]: https://img-blog.csdnimg.cn/20201201115346443.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201201120640401.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz,size_16,color_FFFFFF,t_70