bf算法（串模式匹配算法）c语言详解-百家乐凯发k8

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

主串与子串：如果串 a（如 "shujujiegou"）中包含有串 b（如 "ju"），则称串 a 为主串，串 b 为子串。主串与子串之间的关系可简单理解为一个串 "包含" 另一个串的关系。

实现串的模式匹配的算法主要有以下两种：

1. 普通的模式匹配算法；

2. 快速模式匹配算法；

本节，先来学习普通模式匹配（bf）算法的实现。

bf算法原理

普通模式匹配算法，其实现过程没有任何技巧，就是简单粗暴地拿一个串同另一个串中的字符一一比对，得到最终结果。

例如，使用普通模式匹配算法判断串 a（"abcac"）是否为串 b（"ababcabacabab"）子串的判断过程如下：

首先，将串 a 与串 b 的首字符对齐，然后逐个判断相对的字符是否相等，如图 1 所示：

图 1 串的第一次模式匹配示意图

图 1 中，由于串 a 与串 b 的第 3 个字符匹配失败，因此需要将串 a 后移一个字符的位置，继续同串 b 匹配，如图 2 所示：

图 2 串的第二次模式匹配示意图

图 2 中可以看到，两串匹配失败，串 a 继续向后移动一个字符的位置，如图 3 所示：

图 3 串的第三次模式匹配示意图

图 3 中，两串的模式匹配失败，串 a 继续移动，一直移动至图 4 的位置才匹配成功：

图 4 串模式匹配成功示意图

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

接下来，我们要编写代码实现两个串的模式匹配（图 1 ~图 4）。

bf算法实现

bf 算法的实现思想是：将用户指定的两个串 a 和串 b，使用串的定长顺序存储结构存储起来，然后循环实现两个串的模式匹配过程，c 语言实现代码如下：

#include #include //串普通模式匹配算法的实现函数，其中 b是伪主串，a是伪子串int mate(char * b,char *a){int i=0,j=0;while (i
程序运行结果：
6
注意，在实现过程中，我们借助 i-strlen(a) 1 就可以得到成功模式匹配所用的次数，也就是串 a 移动的总次数。
bf算法时间复杂度
该算法最理想的时间复杂度 o(n)，n 表示串 a 的长度，即第一次匹配就成功。

bf 算法最坏情况的时间复杂度为 o(n*m)，n 为串 a 的长度，m 为串 b 的长度。例如，串 b 为 "0000000001"，而串 a 为 "01"，这种情况下，两个串每次匹配，都必须匹配至串 a 的最末尾才能判断匹配失败，因此运行了 n*m 次。
总结
bf 算法的实现过程很 "无脑"，不包含任何技巧，在对数据量大的串进行模式匹配时，算法的效率很低。

其实，bf 算法还可以改进，就是下节要学的 kmp 算法。