当前位置: 编程技术>c/c++/嵌入式
字符串的模式匹配详解--BF算法与KMP算法
来源: 互联网 发布时间:2014-10-27
本文导语: 一.BF算法 BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符...
一.BF算法
BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果。
举例说明:
S: ababcababa P: ababa BF算法匹配的步骤如下 i=0 i=1 i=2 i=3 i=4 第一趟:ababcababa 第二趟:ababcababa 第三趟:ababcababa 第四趟:ababcababa 第五趟:ababcababa ababa ababa ababa ababa ababa j=0 j=1 j=2 j=3 j=4(i和j回溯) i=1 i=2 i=3 i=4 i=3 第六趟:ababcababa 第七趟:ababcababa 第八趟:ababcababa 第九趟:ababcababa 第十趟:ababcababa ababa ababa ababa ababa ababa j=0 j=0 j=1 j=2(i和j回溯) j=0 i=4 i=5 i=6 i=7 i=8 第十一趟:ababcababa 第十二趟:ababcababa 第十三趟:ababcababa 第十四趟:ababcababa 第十五趟:ababcababa ababa ababa ababa ababa ababa j=0 j=0 j=1 j=2 j=3 i=9 第十六趟:ababcababa ababa j=4(匹配成功)
代码实现:
int BFMatch(char *s,char *p) { int i,j; i=0; while(i