串的模式匹配问题：朴素算法与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(iif (j==0||T[i]==T[j]){++i;++j;next[i]=j;}

else j=next[j];

}

return *next;

}

int Index_KMP(char *S,char *T,int pos){

//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法，其中T非空，1<=pos<=StrLength(S).

int next[100];

*next=get_next(T,next);

int j=1,i=pos;

while(i<=S[0]&&j<=T[0]){

if(j==0||S[i]==T[j]){++i;++j;}

else j=next[j];

}

if(j>T[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\

//printf(\"%d \

do{

printf(\"\\n请输入您需要的任务的序号\");

printf(\"\\n1:朴素的模式匹配算法\");

printf(\"\\n2:快速模式匹配算法\");

printf(\"\\n3:退出\\n\");

scanf(\"%d\

switch(id){

case 1:

{printf(\"\\n\\n你调用了功能1:\");

printf(\"\\n朴素的模式匹配算法\");

k=Index(A,B,j);

printf(\"\\n该位置为：\");

printf(\"%d\\n\

break;}

case 2:

{printf(\"\\n\\n你调用了功能2:\");

printf(\"\\n 快速模式匹配算法\");

a=Index_KMP(A,B,j);

printf(\"\\n该位置为：\");

printf(\"%d\\n\

break;}

case 3:

{printf(\"\\n\\n你调用了功能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(iif (j==0||T[i]==T[j]){++i;++j;next[i]=j;}

else j=next[j];

}

return *next;

}

int Index_KMP(char *S,char *T,int pos){

//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法，其中T非空，1<=pos<=StrLength(S).

int next[100];

*next=get_next(T,next);

int j=1,i=pos;

while(i<=S[0]&&j<=T[0]){

if(j==0||S[i]==T[j]){++i;++j;}

else j=next[j];

}

if(j>T[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\

//printf(\"%d \

do{

printf(\"\\n请输入您需要的任务的序号\");

printf(\"\\n1:朴素的模式匹配算法\");

printf(\"\\n2:快速模式匹配算法\");

printf(\"\\n3:退出\\n\");

scanf(\"%d\

switch(id){

case 1:

{printf(\"\\n\\n你调用了功能1:\");

printf(\"\\n朴素的模式匹配算法\");

k=Index(A,B,j);

printf(\"\\n该位置为：\");

printf(\"%d\\n\

break;}

case 2:

{printf(\"\\n\\n你调用了功能2:\");

printf(\"\\n 快速模式匹配算法\");

a=Index_KMP(A,B,j);

printf(\"\\n该位置为：\");

printf(\"%d\\n\

break;}

case 3:

{printf(\"\\n\\n你调用了功能3:\");

printf(\"\\n退出\\n\");

}

}

}while(id!=3);

}

}