作者：解学武

在《串是什么》一节中，给大家讲解了“子串和主串”的概念。假设字符串 A 为 "shujujiegou"，字符串 B 为 "shuju"，在串 A 中可以找到串 B，因此串 A 和串 B 就具有这样的关系：A 是 B 的主串，B 是 A 的子串。

所谓串的模式匹配算法，是一种专门定位子串在主串中位置的方法（方案、思想），整个定位的过程称为模式匹配。此外，在模式匹配的过程中，子串通常又被称为“模式串”。

串模式匹配的实现方法有很多种，本节先给大家讲一种最容易理解、最简单的方法，称为 BF 算法。

BF算法的实现过程

采用 BF 算法定位模式串在主串中的位置，就是简单粗暴的从主串的起始位置开始，不断地将模式串中的字符和主串中的字符进行对比。

具体来讲，假设对模式串 A（"abcac"）和主串 B（"ababcabacabab"）进行模式匹配，BF 算法的执行过程如下：

1) 将模式串 A 与主串 B 的首字符对齐，逐个判断相对的字符是否相等，如图 1 所示：
2) 图 1 中，由于模式串 A 与主串 B 的第 3 个字符匹配失败，此时将模式串 A 后移一个字符的位置，采用同样的方法重新匹配，如图 2 所示：
3) 图 2 中可以看到，两个串依旧匹配失败，模式串 A 继续后移一个字符的位置，如图 3 所示：
4) 图 3 仍然匹配失败，模式串 A 继续向后移动，一直移动至图 4 的位置才匹配成功：
从图 1 到图 4，模式串 A 与主串 B 共匹配了 6 次才成功，最终定位到模式串 A 位于主串 B 第 6 的位置处，整个模式匹配的过程就称为 BF 算法。

BF算法的具体实现

实现 BF 算法，首先要想好如何存储模式串和主串。我们知道，串的存储结构有三种，分别是定长顺序存储、堆分配存储和块链存储。在 BF 算法中，这三种存储结构都可以使用，最常用的是定长顺序存储结构和堆分配存储结构。

本节我们使用定长顺序存储结构来存储模式串和主串，BF 算法的 C 语言实现代码如下：

#include <stdio.h>
#include <string.h>
#define STR_LEN 100
typedef char myString[STR_LEN];
//串普通模式匹配算法的实现函数，其中 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 向后移动一位，j 重置
            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 -1;
}
int main() {
    myString B = "ababcabcacbab";
    myString A = "abcac";
    int res = mate(B, A);
    if (res == -1) {
        printf("模式匹配失败，主串中不含模式串\n");
    }
    else
    {
        printf("匹配成功，主串中定义到模式串的位置为：%d", res);
    }
    return 0;
}

程序运行结果：

6

程序中，借助 i-strlen(A)+1 就可以得到成功模式匹配的次数，也就是模式串在主串中的位置。

BF算法的时间复杂度

BF 算法执行效率最高的理想情况是第一次模式匹配就成功了，While 循环只执行 n 次（n 为模式串的长度），对应的时间复杂度为O(n)。

BF 算法最坏情况下的时间复杂度为 O(n*m)。举个简单的例子，假设模式串 A 为 "01"，它的长度为 2；主串 B 为 "000000001"，它的长度为 9,两个串模式匹配时，while 循环共执行了 2*8 次，近似等于 n*m 次。

总结

BF 算法的实现过程很 "无脑"，不包含任何技巧。实际上，我们可以对 BF 算法的实现过程进行改进，下一节会给大家讲解 BF 算法的一个改进版本，称为 KMP 算法。

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。