串匹配算法——BF算法
串匹配算法——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算法。
版权声明：本文为xyhj原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。