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实现