串匹配算法——BF算法

串匹配问题:

串模式匹配，简称串匹配，是数据结构中的经典问题，在邓俊辉版数据结构中，他的定义如下：

对基于同一字符表的任何文本串T（|T| = n）和模式串P（|P| = m），判定T中是否存在某一子串与P相同，若存在（匹配），则报告该子串在T中的起始位置。

一般来说文本串T的长度n要远大于模式串P的长度m。到目前为止，有五花八门各种各样的串匹配算法，下面介绍一种最简单的蛮力算法。

蛮力算法(Brute Force)

在所有字符串匹配算法中，BF算法是最直接，最符合人直觉的算法，它只需要顺序地从文本串T中截取长度为m的子串t，再将这个子串和模式串P逐字母的比较就可以了。

选取子串

用两个指针i和j分别指向子串和模式串，比较对应的字符

如果对应的字符相等，如图，$t[i] = P[j]$,则i和j各自前进一位。

如果$t[i] \ne P[j]$，说明该子串和模式串不匹配

于是放弃该子串，在T中顺序选择下一个子串，重新开始上面的匹配过程。

当指向模式串P的指针j遍历完模式串后，说明所有的字符都匹配成功，那这个子串就找到了，返回这个位置就可以了。

字符串匹配的代码如下:

1 #include<stdio.h>
 2 #include<string.h>
 3 int BF(char*T,char*P)
 4 {
 5     int i,j;
 6     int m = strlen(P),n = strlen(T);
 7     printf("%d %d\n",m,n);
 8     i = j =0;
 9     while(j<m&&i<n)
10     {
11         if(P[j]==T[i])
12             i++,j++;
13         else
14         {
15             i = i-j+1;
16             j = 0;
17         }
18         if(j==m)
19             return i-j;
20     }
21     return -1;
22 }
23 int main()
24 {
25     char*T = "ABCDESABCDFAB";
26     char*P = "ABCDF";
27     int indexof = BF(T,P);
28     printf("%d\n",indexof);
29     return 0;
30 }

时间复杂度分析

不难发现，文本串T至多有n-m+1个子串，每轮最多进行m次计较，所以最多需要比较$m*(n-m+1)$次，所以它的时间复杂度为$O(nm)$。最好的情况是每经一次比对就发现不匹配，这种情况下，BF算法的时间复杂度下降为$O(n)$，但是这种情况比较难出现。

BF算法虽然简单，但是在最坏情况下所需的时间，是文本串长度和字符串长度的乘积，当文本串很长时，它的时间复杂度会非常高，所以我们需要更加高效的算法。下一篇博客将介绍更高效的KMP算法。

发表于

2021-03-29 21:30

行运换甲

阅读(116)

编辑