是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配，若相等，则继续比较S的第二个字符和P的第二个字符；若不相等，则比较S的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果。
32BF算法的实现
将主串S中某个位置i起始的子串和模式串T相比较。即从j0起比较Sij与Tj，若相等，则在主串S中存在以i为起始位置匹配成功的可能性，继续往后比较j逐步增1，直至与T串中最后一个字符相等为止，否则改从S串的
2
f下一个字符起重新开始进行下一轮的匹配，即将串T向后滑动一位，即i增1，而j退回至0，重新开始新一轮的匹配。
33
BF算法举例
在串S“abcabcabdabba”中查找T“abcabd”（我们可以假设从下标0开始）先是比较S0和T0是否相等，然后比较S1和T1是否相等。我们发现一直比较到S5和T5才不等。如图：
当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S下标增1然后再次比较。如图：
这次立刻发生了失配，T下标又回溯到开始，S下标增1然后再次比较。如图：
又一次发生了失配，所以T下标又回溯到开始，S下标增1然后再次比较。这次T中的所有字符都和S中相应的字符匹配了。函数返回T在S中的起始下标3。如图：
3
f4KMP匹配算法
41KMP算法举例
还是相同的例子，在S”abcabcabdabba”中查找T”abcabd”，如果使用KMP匹配算法，当第一次搜索到S5和T5不等后，S下标不是回溯到1，T下标也不是回溯到开始，而是根据T中T5‘d’的模式函数值，直接比较S5和T2是否相等，因为相等，S和T的下标同时增加因为又相等，S和T的下标又同时增加。最终在S中找到了T。如图：
42KMP算法的实现
在前面的例子。T5‘d’的模式函数值等于2（
ext52），其实这个2表示T5‘d’的前面有2个字符和开始的两个字符相同，且T5‘d’不等于开始的两个字符之后的第三个字符（T2‘c’）如图：
也就是说，如果开始的两个字符之后的第三个字符也为‘d’那么，尽管T5‘d’的前面有2个字符和开始的两个字符相同，T5‘d’的模式函数值也不为2，而是为0。
4
fS4T4，S3T3，根据
ext52，有T3T0，T4T1，所以S3T0，S4T1（两对相当于间接比较过了），因此，接下来比较S5和T2是否相等。
43KMP匹配算法和简单匹配算法效率比较
一个极端的例子是：在S“AAAAAAAB“100个A中查找T”AAAAAAAAAB”简单匹配算法每次都是比较到Tr