【数据结构】串模式匹配算法

#include
#include#define maxn 100000/*
bacbababadababacamba
ababacaaaabaaaab
aaaab
*//*菜单二：输出各趟匹配的详细过程、匹配总趟数、单个字符比较次数、匹配成功时的位置序号或匹配失败提示信息菜单三：输出next[]各元素数值、各趟匹配详细过程、匹配总趟数、单个字符比较次数、匹配成时的位置序号或匹配失败提示信息菜单四：输出nextval[]各元素数值、各趟匹配详细过程、匹配总趟数、单个字符比较次数、匹配成时的位置序号或匹配失败提示信息 
*/ char s[100],t[100],ss[maxn],tt[maxn]; 	//主串与模式串,ss与pp为了检验子串与主串的长度 
int next[maxn],nextval[maxn],chcom[maxn];	//chcom数组记录字符比较次数 void print(); 
void Input();
void init();	//初始化各个数组 
void BF();
void KMP(int y);
void get_next();
void get_nextval();
int jiancei();int main(){while(1){char i[100];print();scanf("%s",&i[0]);if(strlen(i)!=1||i[0]<'0'||i[0]>'4'){		//检验输入printf("输入错误，请输入0-4中的数字\n");continue;}if(i[0]=='1'){Input();}else if(i[0]=='2'&&strlen(s)!=0&&strlen(t)!=0){BF();}else if(i[0]=='3'&&strlen(s)!=0&&strlen(t)!=0){get_next();KMP(0);}else if(i[0]=='4'&&strlen(s)!=0&&strlen(t)!=0){get_nextval();KMP(1);}else if(i[0]=='0'){printf("系统退出,感谢使用\n");break;}else if(strlen(s)==0||strlen(t)==0){printf("请先输入主串和模式串之后再进行匹配！\n");}else{printf("输入错误，请输入0-4中的数字\n");continue;}}	return 0;
}void print(){printf("**************************************************\n");printf("*        1.输入主串、子串                        *\n");printf("*        2.朴素的模式匹配算法                    *\n");printf("*        3.KMP算法(Next[])                       *\n");printf("*        4.KMP改进算法(NextVal[])                *\n");printf("*        0.退出管理系统                          *\n");printf("--------------------------------------------------\n");     	printf("         请输入你要选择的功能:\n");
} void Input(){printf("请输入主串:");getchar();scanf("%[^\n]",ss);		// \n作为字符串输入的结束符,不能用%s,否则会把“ ”当作结束符 if(strlen(ss)>100){printf("主串长度应不大于100，请重新输入！\n");Input();}printf("请输入子串:");scanf("%s",tt);if(strlen(tt)>100){printf("模式串长度应不大于100，请重新输入！\n");Input();}int i;for(i=0;ss[i]!='\0';i++){s[i]=ss[i];printf("%c",s[i]); }  s[i]='\0';printf("\n");for(i=0;tt[i]!='\0';i++){t[i]=tt[i];printf("%c",t[i]);}t[i]='\0';printf("\n"); int m=strlen(s);int n=strlen(t);if(mm||n<1){printf("输入有误,请重新输入1-%d之间的数字\n",m);fflush(stdin);	}}while(ret!=1||n>m||n<1);//cout<<"输入的值为"<n){printf("字符串匹配成功，匹配总趟数为%d,位置序号为%d\n",i-n,i-n);printf("----------------------------------------------------------------------------------------------\n");for(int x=0;xn){printf("字符串匹配成功，匹配总趟数为%d,位置序号为%d\n",r+1,i-n); printf("----------------------------------------------------------------------------------------------\n");for(int x=0;x

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！