C语言数据结构中串的模式匹配

C语言数据结构中串的模式匹配

串的模式匹配问题：朴素算法与KMP算法

#include
#include
int Index(char *S,char *T,int pos){
//返回字串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0.
//其中，T非空，1<=pos<=StrLength(s).
int i=pos;
int 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 get_next(char *T,int next[]){
//求模式串T的next函数值并存入数组next。
int i=1;next[1]=0;int j=0;
while(iT[0]) return i-T[0];
else return 0;
}
void main()
{
int id,j,k,i,a;
printf("输入主串、子串和匹配起始位置n");
char A[20];char B[10];
printf("请输入主字串内容n");
    gets(A+1);
    *A=strlen(A+1);
printf("请输入子字串内容n");
    gets(B+1);
    *B=strlen(B+1);
printf("请输匹配起始位置n");
    scanf("%d",&j);
//printf("%d ",k);
    do{
printf("n请输入您需要的任务的序号");
printf("n1:朴素的模式匹配算法");
printf("n2:快速模式匹配算法");
printf("n3:退出n");
scanf("%d",&id);
    switch(id){
case 1:
    {printf("nn你调用了功能1:");
    printf("n朴素的模式匹配算法");
    k=Index(A,B,j);
    printf("n该位置为：");
    printf("%dn",k);
    break;}     
case 2:
    {printf("nn你调用了功能2:");
printf("n 快速模式匹配算法");
a=Index_KMP(A,B,j);
printf("n该位置为：");
printf("%dn",a);
break;}
case 3:
    {printf("nn你调用了功能3:");
printf("n退出n");
}
    }
}while(id!=3);

#include
#include
int Index(char *S,char *T,int pos){
//返回字串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0.
//其中，T非空，1<=pos<=StrLength(s).
int i=pos;
int 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 get_next(char *T,int next[]){
//求模式串T的next函数值并存入数组next。
int i=1;next[1]=0;int j=0;
while(iT[0]) return i-T[0];
else return 0;
}
void main()
{
int id,j,k,i,a;
printf("输入主串、子串和匹配起始位置n");
char A[20];char B[10];
printf("请输入主字串内容n");
    gets(A+1);
    *A=strlen(A+1);
printf("请输入子字串内容n");
    gets(B+1);
    *B=strlen(B+1);
printf("请输匹配起始位置n");
    scanf("%d",&j);
//printf("%d ",k);
    do{
printf("n请输入您需要的任务的序号");
printf("n1:朴素的模式匹配算法");
printf("n2:快速模式匹配算法");
printf("n3:退出n");
scanf("%d",&id);
    switch(id){
case 1:
    {printf("nn你调用了功能1:");
    printf("n朴素的模式匹配算法");
    k=Index(A,B,j);
    printf("n该位置为：");
    printf("%dn",k);
    break;}     
case 2:
    {printf("nn你调用了功能2:");
printf("n 快速模式匹配算法");
a=Index_KMP(A,B,j);
printf("n该位置为：");
printf("%dn",a);
break;}
case 3:
    {printf("nn你调用了功能3:");
printf("n退出n");
}
    }
}while(id!=3);
 
}

 感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！