详解bf算法.docx

算法原理??BF(Brute Force)算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配，若相等，则继续比较S的第二个字符和P的第二个字符；若不相等，则比较S的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果。 BF算法是一种蛮力算法。????举例说明：????S:? ababcababa????P:??ababa??? BF算法匹配的步骤如下：（2）代码实现#include?stdio.h#include?string.h?int?BFMatch(char?*s,char?*p){????int?i,j;??? i =0;????while(i ?strlen(s))??? {???????j =?0;???????while(s[i] == p[j] jstrlen(p))???????{???????????i++;???????????j++;???????}? ??????if(strlen(p) == j)???????{???????????return?i -?strlen(p);???????}????????i = i - j +?1;????????????????//?指针i回溯??? }?????return?-1;}int?main(){????char?*szSource =?ababcababa;????char?*szSub =?ababa;????int?index =BFMatch(szSource, szSub);????printf(目标串包含匹配串的起始位置：%d,index);}（3）运算过程(a) i=0, j=0, s[0]==p[0];??? i=1,j=1, s[1]==p[1];??? i=2,j=2, s[2]==p[2];??? i=3,j=3, s[3]==p[3];??? i=4,j=4, s[[4]!=p[4], 第一次循环结束，i=4-4+1=1(b) i=1, j=0, s[1]!=p[0],第二次循环结束, i=1-0+1=2(c) i=2, j=0, s[2]==p[0];?? i=3, j=1, s[3]==p[1];?? i=4, j=2, s[4]!=p[2]; 第三次循环结束，i=4-2+1=3(d) i=3, j=0, s[3]!=p[0];第四次循环结束，i=3-0+1=4(e) i=4, j=0, s[4]!=p[0];第四次循环结束，i=4-0+1=5(f) i=5, j=0, s[5]==p[0];?? i=6, j=1; s[6]==p[1];?? i=7, j=2, s[7]==p[2];?? i=8, j=3, s[8]==p[3];?? i=9, j=4, s[9]==p[4];?? i=10, j=5, j==strlen(p), 最后一次循环结束，返回i-strlen(p) = 5?（4）运行结果目标串包含匹配串的起始位置：5