算法字符串匹配-BF算法

欢迎点击「算法与编程之美」关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

字符串是数据结构中比较简单的一种，但又是我们最常用的数据结构之一。对于字符串对象，最重要的操作之一便是字符串匹配（查找），本篇文章便向大家介绍一个典型的匹配算法—BF算法

为了方便理解，我们直接从问题入手，来理解这两种算法。

BF算法

目标串：BBC ABCDAB ABCD ABCDABDE

模式串：ABCDABD

提示：（空格也是一个字符串）

问题：查看模式串是否出现在目标串中，并找出其在目标串中的下标位置

分析：大家在碰到这个问题时，要如何解决呢？思考一下，下面讲解BF算法，其实也就是大多人都会想到的方法

思路概况：

将模式串的第一位字符与目标串的第一位字符比较，匹配成功，则将模式串第二位字符与目标串第二位字符比较……若不匹配，则将模式串向右移一位，与目标串继续比较。

例如此题，将模式串第一位字符A与目标串第一位字符B比较，匹配失败，将模式串第一位字符A与目标串第二位字符B比较，依此类推，得出结构。

详细算法思路：

用i和j分别表示目标串和模式串当前待比较字符的位置（下文的i和j均为此意），以此题为例，初始时，i为目标串的第一个字符B，j为模式串的第一个字符A。

若模式串中仍存在未比较的字符且目标串中剩余未比较字符的长度大于或等于模式串的长度，就执行下面的（3）~（7）；否则执行（8）

记录当前目标串的下标i

判断模式串当前比较位置的字符是否相等

若（4）相等，就执行（6），否则执行（7）

将i和j分别执行加1操作，并执行（4）

将（3）中的值加1并赋值给i，再将j的值修改为0，执行（2），继续匹配。

输出字符串匹配失败

注意：

很多人在自己思考这个问题时，会犯一个错误。以此题为例：

蓝色表示匹配成功的字符，红色表示匹配失败的字符

目标串：BBC ABCDABABCDABCDABDE

模式串：ABCDABD

在模式串与目标串红色位置做比较时，因为模式串最后一位D会与目标串的空格作比较，匹配失败。很多人就会想，直接从匹配失败的这一位开始，继续下一次匹配，但这样可能会导致出错。

举个例子，当匹配到目标串中的蓝色部分时，由于最后一位不同，匹配失败。如果直接从匹配这一位或者下一位开始继续匹配，就会错过正确答案（目标串中下划线部分）

结束语：小伙伴若还有疑问，可在文章下方评论提出，小编会及时回复，感谢观看。