③54正文匹配模式 算法56 int find bF(char*S,char*P, int start) start;j=0 while (s[]=\0&& Pll!= 0) f(S[=Pj]){++j++ else (i=i-j+1; j=0; 3 if (P[]==0)return(i-j else return -1 例:S=“ ababcabcacbab”T=“ abac”返回值=5 算法复杂度:O(mxn)与首字母在S中的出现概率有关 ypb@ustc.edu.cn 9 中国科学技术大学ypb@ustc.edu.cn 9 中国科学技术大学 5.4正文匹配模式 • 算法5.6 int find_BF (char *S,char *P,int start) { i = start; j = 0; while ( S[i] != '\0' && P[j] != '\0' ) if ( S[i] == P[j] ) {i++;j ++;} else { i =i-j+1; j = 0; } if ( P[j] == '\0' ) return (i-j); else return -1; } – 例：S＝ “ababcabcacbab” T=“abcac” 返回值＝5 – 算法复杂度：O(m×n) 与首字母在S中的出现概率有关