大话数据结构-5 串
串的匹配模式
串S和T存在,T是非空串, l<=pos<=s.strLength (s) 若主串S中存在和串T值相同的子串, 则返回它在主串S中 第pos个字符之后第一次出现的位置 , 否则返回0。
朴素的模式匹配
``` /* 朴素的模式匹配:基本数组实现 假设主串S和要匹配的子串T的长度存在S[0]与T[0]中 */ /*返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。 T非空,1≤pos≤StrLength (s)*/ int Index(String S,String T,int pos) { 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;//i退回到上次匹配首位的下一位 j=1;//j退回到子串T的首位 } } if(j>T[0]){ return i-T[0]; }else{ return 0; } } ```
KMP模式匹配
``` /* KMP模式匹配算法实现 */ //通过计算返回子串T的next数组。 //char T[100] = "xxxxxx";字符串的本质就是数组 void get_next(char *T,int *next) { int i,j; i=1;//因为T[0]存储了T的长度,所以从1开始 j=0;//next值 next[1]=0;//next数组从下标为1开始 默认next[0]=0 while(i<T[0]){//T[0]表示串T的长度 if(j==0||T[i]==T[j]){ i++; j++; next[i]=j; }else{ //若T[i]!=T[j]字符不相同,则回溯...->0 j = next[j]; } } } //返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。 //T非空,1SposSStrLength(s)。 int Index_KMP(String S,String T,int pos) { int i = pos;//i用于主串S当前位置下标值 int j=1;//j用于子串T中当前位置下标值 int next[255]; get_next(T,next);//对串T作分析,得到next数组 while(i<=S[0] && j<=T[0]){ if(j==0||S[i] == T[j]){ ++i; ++j; }else{ j = next[j];//j T的对比位置退回到next中的位置 } } if(j>T[0]){ return i-T[0]; }else{ return 0; } } ```
KMP 模式匹配算法改进
``` /* KMP 模式匹配算法改进 get_next()——>get_nextval() Index_KMP()不变 */ //通过计算返回子串T的next数组。 //char T[100] = "xxxxxx";字符串的本质就是数组 void get_nextval(char *T,int *next) { int i,j; i=1;//因为T[0]存储了T的长度,所以从1开始 j=0;//next值 next[1]=0;//next数组从下标为1开始 默认next[0]=0 while(i<T[0]){//T[0]表示串T的长度 if(j==0||T[i]==T[j]){ /* T[i]表示后缀的单个字符,*/ /* T[j]表示前缀的单个字符*/ i++; j++; if(T[i]!=T[j]){//若当前字符与前缀字符不同 next[i]=j;//则当前的门为nextval在i位置的值 }else{ next[i] = next[j];//如果与前缀字符相同,则将前缀 //字符的nextval值赋值给nextval在i位置的值 } }else{ //若T[i]!=T[j]字符不相同,则回溯...->0 j = next[j]; } } } //返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。 //T非空,1SposSStrLength(s)。 int Index_KMP(String S,String T,int pos) { int i = pos;//i用于主串S当前位置下标值 int j=1;//j用于子串T中当前位置下标值 int next[255]; get_nextval(T,next);//对串T作分析,得到next数组 while(i<=S[0] && j<=T[0]){ if(j==0||S[i] == T[j]){ ++i; ++j; }else{ j = next[j];//j T的对比位置退回到next中的位置 } } if(j>T[0]){ return i-T[0]; }else{ return 0; } } ```