字符串匹配（BF算法和KMP算法及改进KMP算法）

深碍√TFBOYSˉ_ 2023-06-21 10:26 71阅读 0赞

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include<cstring>
    #include<iostream>
    using namespace std;
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef int Status;
    #define MAXSTRLEN 255   		//用户可在255以内定义最长串长
    typedef char SString[MAXSTRLEN+1];		//0号单元存放串的长度
    
    Status StrAssign(SString T, char *chars) {
         //生成一个其值等于chars的串T
    	int i;
    	if (strlen(chars) > MAXSTRLEN)
    		return ERROR;
    	else {
        
    		T[0] = strlen(chars);
    		for (i = 1; i <= T[0]; i++)
    			T[i] = *(chars + i - 1);
    		return OK;
    	}
    }
    
    void get_next(SString T, int next[]){
         //求模式串T的next函数值并存入数组next
    	int i = 1, j = 0;
    	next[1] = 0;
    	while (i < T[0])
    		if (j == 0 || T[i] == T[j])
    		{
        
    			++i;
    			++j;
    			next[i] = j;
    		}//abssgaaadaaaadcf aaaad 0
    		else
    			j = next[j];
    	for(i=1;i<strlen(T);i++)
    		printf("j=%d  next[%d]=%d \n",i,i,next[i]);//abssgaaadaaaadcf aaaad 0
    }//get_next
    
    void get_nextval(SString T, int nextval[]){
         // 求模式串T的next函数修正值并存入数组nextval
    	int i = 1, j = 0;
    	nextval[1] = 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];
    	for(i=1;i<strlen(T);i++)
    		printf("j=%d  nextval[%d]=%d \n",i,i,nextval[i]);
    }//get_nextval
    //
    void BF(char s[100],char p[50],int t){
        
    	int space,a,b,k=0,num=0;
    	int pos, i, j, flag;
    	j = flag = 0;
    	if(strlen(s)<strlen(p)){
        
    	    printf("Error:子串长度大于父串.\n"); 
    	    return ;
    	}
    	if(strlen(s)-strlen(p)<t){
        
    		printf("Error:匹配位置不合适.\n");
    		return ;
    	}
    	space=i=pos=t;
    	printf("\n");
    	while(i < strlen(s))
        {
        
        	if(j==0&&s[i]!=p[j])
        		num++;
    		pos=i;
            if(p[j] == s[i]){
        
                while(j < strlen(p))
                {
        
                    if(p[j] != s[i]) 
    				{
        	
    					k++;
    					printf("%s   %d    此次匹配失败\n",s,k);
    					for(a=space;a>0;a--)
    	    				printf(" ");//输出详细过程 
    	    			for(b=0;b<=j;b++)
    	    				printf("%c",p[b]);//aaadddawawdcw awd 0
    	    			printf("\n");
    					break;
    				}
    				else{
        
                    	k++;
    					printf("%s   %d    此次匹配成功\n",s,k);
    			    	for(a=space;a>0;a--)
    			    		printf(" ");//输出详细过程 
    			    	for(b=0;b<=j;b++)
    			    		printf("%c",p[b]);
    			    	printf("\n");
    					i++;
                    	j++;
    				}
                }
                if(j == strlen(p))
                    flag = 1;
            }
            else{
        
    	    	k++;
            	printf("%s   %d    此次匹配失败\n",s,k);//aaadddawawdcw awd 0
            	for(a=space;a>0;a--)
    	    		printf(" ");
    	    	printf("%c\n",p[j]) ;
    		} 
        	space++;
            if(flag == 1){
        //如果匹配成功，flag=1，则进入此句； 
                printf("匹配位置为：%d\n", pos);
                break;
            }
            //开始下一轮的循环，对某些变量进行初始化
            i = ++pos;
            j = 0;
            if(i > strlen(s) - strlen(p)){
        
                printf("主串中不存在此子串！\n");
                break;
            }
        } 
        printf("共匹配%d次\n",k);
        printf("单个字符匹配次数为%d\n",num);
    }
    
    int KMP(SString S, SString T, char* s, char* p, int pos, int next[]){
         	// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
    	//其中，T非空，1≤pos≤StrLength(S)
    	if(strlen(s)<strlen(p)){
        
    	    printf("Error:子串长度大于父串.\n"); 
    	    return -1;
    	}
    	if(strlen(s)-strlen(p)<pos){
        
    		printf("Error:匹配位置不合适.\n");
    		return -1;
    	}
    	int i = pos, j = 1,k=0,a,b,space=0;
    	while (i <= S[0] && j <= T[0])
    	{
        
    		if (j == 0 || S[i] == T[j]) // 继续比较后继字
    		{
        
    			i++;
    			j++;
    			if(j == strlen(T))
    			{
        	//	进入此if语句即表示匹配成功
    				printf("共循环%d次\n",k);
    				break;
    			}
    				
    			++k;
    			printf("%s   %d  next[%d]=%d  \n",s,k,j,next[j]);
    			for(a=space;a>0;a--)
    				printf(" ");
    			for(b=1;b<=j;b++)
    				printf("%c",T[b]);//abssgaaadaaaadcf aaaad 0
    			printf("\n");		
    			if(j==1&&S[i]!=T[j]) simple++;//记录单字符匹配失败的次数。 
    		}
    		else j = next[j];// 模式串向右移动
    		space=i-j; //输出子串前面的空格数 
    	}
    	printf("单字符循环%d次\n",simple);
    	if (j > T[0]) // 匹配成功
    		return i - T[0];
    	else
    		return -1;
    }//Index_KMP
    
    int main(){
        
    	printf("1.输入主串、子串和匹配起始位置\n2.BF算法\n3.KMP算法\n4.KMP改进算法\n0.退出\n");
    	int t = -1,place;
    	SString S;//abssgaaadaaaadcf aaaad 0
    	SString T;
    	int *next,*nextval;
    	char s[50], p[50];
    	while(t)
    	{
        
    		printf("请输入：");
    		scanf("%d",&t);
    		switch(t)
    		{
        
    			case 0:
    				break;
    			case 1:
    				printf("请输入主串、子串和匹配起始位置：\n");
    				scanf("%s%s%d",s,p,&place);
    				StrAssign(S,s) ;
    				StrAssign(T,p) ;
    				break;
    			case 2:
    				BF(s,p,place);
    				break;
    			case 3:
    				next = new int[T[0]+1];
    				get_next(T,next);
        			printf("匹配的位置为 %d\n",KMP(S,T,s,p,place,next));
        			break;
        		case 4:
        			nextval = new int[T[0]+1];
    				get_nextval(T,nextval) ;
    				printf("匹配的位置为 %d\n",KMP(S,T,s,p,place,nextval));
    				break;
    			default:
    				break;
    		}
    	}
        return 0;
    }