写在前面：博主是一位普普通通的19届双非软工在读生，平时最大的爱好就是听听歌，逛逛B站。博主很喜欢的一句话花开堪折直须折，莫待无花空折枝：博主的理解是头一次为人，就应该做自己想做的事，做自己不后悔的事，做自己以后不会留有遗憾的事，做自己觉得有意义的事，不浪费这大好的青春年华。博主写博客目的是记录所学到的知识并方便自己复习，在记录知识的同时获得部分浏览量，得到更多人的认可，满足小小的成就感，同时在写博客的途中结交更多志同道合的朋友，让自己在技术的路上并不孤单。

目录:
1.BF算法原理
2.BF算法代码实现
3.BF算法的时间复杂度

1.BF算法原理

BF算法是串的模式匹配算法，通俗地理解，是一种用来判断两个串之间是否具有"主串与子串"关系的算法

普通模式匹配算法，其实现过程没有任何技巧，就是简单粗暴地拿一个串同另一个串中的字符一一比对，得到最终结果。例如，使用普通模式匹配算法判断串 A（“abcac”）是否为串 B（“ababcabacabab”）子串的判断过程如下：首先，将串 A 与串 B 的首字符对齐，然后逐个判断相对的字符是否相等，如图 所示：

上图第一次匹配失败是由于串 A 与串 B 的第 3 个字符匹配失败，因此需要将串 A 后移一个字符的位置，继续同串 B 匹配：

上图第二次匹配失败，串 A 继续向后移动一个字符的位置：

两串的模式匹配失败，串 A 继续移动，最终到下图：

由此，串 A 与串 B 以供经历了 6 次匹配的过程才成功，通过整个模式匹配的过程，证明了串 A 是串 B 的子串（串 B 是串 A 的主串）。

2.BF算法代码实现

#include <stdio.h> #include <string.h> //串普通模式匹配算法的实现函数，其中 B是伪主串，A是伪子串 int mate(char * B,char *A){int i=0,j=0;while (i<strlen(B) && j<strlen(A)) {if (B[i]==A[j]) {i++;j++;}else{i=i-j+1;j=0;}}//跳出循环有两种可能，i=strlen(B)说明已经遍历完主串，匹配失败；j=strlen(A),说明子串遍历完成，在主串中成功匹配if (j==strlen(A)) {return i-strlen(A)+1;}//运行到此，为i==strlen(B)的情况return 0; } int main() {int number=mate("ababcabcacbab", "abcac");printf("%d",number);return 0; } 运行结果：6

3.BF算法的时间复杂度

该算法最理想的时间复杂度 O(n)，n 表示串 A 的长度，即第一次匹配就成功。
BF 算法最坏情况的时间复杂度为 O(nm)，n 为串 A 的长度，m 为串 B 的长度。例如，串 B 为 “0000000001”，而串 A 为 “01”，这种情况下，两个串每次匹配，都必须匹配至串 A 的最末尾才能判断匹配失败，因此运行了 nm 次。

总结

以上是生活随笔为你收集整理的解析BF(普通串模式匹配算法)算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。