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

#include"c1.h" #include"c2.h" #include"c3.h" Status StrAssign(SString S,char chars[MAX_STR_LEN],int i) { int j; if(i>MAX_STR_LEN) return ERROR; else{ S[0]=i; //printf("%d",S[0]); for(i=1;i<=S[0];i++){ S[i]=chars[i-1]; //printf("%c",S[i]);检验是否将chars赋给S } return OK; } } int Index(SString S,SString T,int pos)//简单的模式匹配 { int i,j; int m=0;//检测比较次数 if(1<=pos&&pos<=S[0]){ i=pos; j=1; while(i<=S[0]&&j<=T[0]){ if(S[i]==T[j]){ i=i+1; j=j+1; } else{ i=i-j+2; j=1; ++m;//如果有一个字母不匹配，则又重新比较，所以比较次数加1 } } if(j>T[0]){ printf("比较次数为：%d\n",m+1);//在最后找到匹配时，少加一次比较，所以m+1 return i-T[0]; } else{ printf("比较次数为：%d\n",m); return 0; } } else{ printf("比较次数为：%d\n",m); return -1; } } int Index_KMP(SString S,SString T,int pos)//KMP模式比较 { int i,j; int k,l; int n=0; char next[40]; //求next[j] k=1; next[1]=0; l=0; while(k<T[0]){ if(l==0||T[k]==T[l]){ ++k; ++l; next[k]=l; } else l=next[l]; } if(1<=pos&&pos<=S[0]){ i=pos; j=1; while(i<=S[0]&&j<=T[0]){ if(j==0||S[i]==T[j]){ i=i+1; j=j+1; } else{ j=next[j]; ++n; } } if(j>T[0]){ printf("比较次数为：%d\n",n+1); return i-T[0]; } else{ printf("比较次数为：%d\n",n); return 0; } } else{ printf("比较次数为：%d\n",n); return -1; } }