4.3串的模式匹配算法 BF算法 int Index BF char S []char T[],int pos){ i=pos-1;j=0; while (S[i+j]!=0'&&T[j]!=10') if(S[itj订=T[])j+; else {i++;j=0;) if T[j]=0')return i+1; else return -1;} -例：S="ababcabcacbabi”T-“abcac”返▣值=6 、 算法复杂度：O(m×n)与首字母在$中的出现概率有关 采用SString实现 ypb@ustc.edu.cn 6 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 4.3串的模式匹配算法 • BF算法 int Index_BF ( char S [ ], char T [ ], int pos ) { i = pos-1; j = 0; while ( S[i+j] != '\0' && T[j] != '\0' ) { if ( S[i+j] == T[j] ) j ++; else { i ++; j = 0; }} if ( T[j] == '\0' ) return i+1; else return -1;} – 例：S＝ “ababcabcacbab” T=“abcac” 返回值＝6 – 算法复杂度：O(m×n) 与首字母在S中的出现概率有关 – 采用SString实现
匹配模式的改进算法*(KMP算法 0 j1时 next[j]= max{k1<k≤j且'p1…pk-1'-p-k+I…P-'} 1其他情况 next[]表示当模式中第个字符与主串失配时，在模式 中需要重新和主串该字符进行比较的字符位置 >模式匹配算法 int Index KMP(SString S,SString T,int pos){ i-pos;j=1; while(i<=S[O]&&j<=T[Ol) if0j=0‖S[的==T]){+i++j} else j=next[j]; if(j>T[O])return i-T[O];else return 0; 一主串指针不回溯。 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 0 j=1时 next[j]= max{k|1<k<j 且’p1…pk-1 ’=’pj-k+1…pj-1 ’} 1 其他情况 next[j]表示当模式中第j个字符与主串失配时，在模式 中需要重新和主串该字符进行比较的字符位置 ➢ 模式匹配算法 int Index_KMP(SString S,SString T,int pos){ i=pos; j=1; 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; } – 主串指针不回溯。 匹配模式的改进算法*(KMP算法)
>获得next数组的算法 void get next(Sstring T,int &next[]){ i=1;next[1]=0;j=0; while(i<T[0]){ ifGj==0‖T[i=T[j]){++i,++j;nex[门=j;} else j=next[j]; >改进后获得next数组(nextval)算法 (红色部分改写如下) if(T[i]!=T[j])nextval[i]=j; else nextval[i]=nextval[j]; ypb@ustc.edu.cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学 ➢获得next数组的算法 void get_next(Sstring T,int &next[]){ i=1; next[1]=0; j=0; while(i<T[0]){ if(j==0 || T[i]==T[j]){++i; ++j;next[i]=j;} else j=next[j]; } } ➢改进后获得next数组(nextval)算法 （红色部分改写如下) if(T[i]!=T[j])nextval[i]=j; else nextval[i]=nextval[j];
4.3数组 数组的定义 ADT Array{ 数据对象：D={aa2.na2.an∈El emset,. j=0,1,b:-1bi是数组第i维的长度，n是位数} 数据关系：R={R,R2Rn} Riaji...aji.ain,aj...jiin aj1…aji…an,aj1.aitl.an∈D,i=2,3n 0<=jk<=bk-1,1<=k<=n,k!=l 0<=j=b-1} ypb@ustc.edu.cn 9 中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 4.3数组 数组的定义 ADT Array{ 数据对象：D={aj1 aj2…ajn| aj1 aj2…ajn∈Elemset, ji=0,1,…bi-1,bi是数组第i维的长度，n是位数} 数据关系：R={R1 ,R2…Rn} Ri={< aj1…aji…ajn , aj1…aji+1…ajn >| aj1…aji…ajn , aj1…aji+1…ajn ∈D,i=2,3…n 0<=jk<=bk-1,1<=k<=n,k!=I 0<=ji<=bi-1 }