天天看点

数据结构模式匹配——BF算法

基本思想:

从主串S的第0个字符开始和模式T的第0个字符进行比较,若相等则继续比较两者的后续字符;

否则,从主串S的第一个字符开始和模式T的第0个字符进行比较,重复上述过程,直到T中的字符全部比较完毕,则说明比较失败。

数据结构模式匹配——BF算法

1.在串S和串T中设比较的起始下标I和j;

2.循环知道S或T的所有字符比较完;

2.1如果s[i]==T[j],继续比较S和T的下一个字符;

2.2否则,将i和j回溯(i=i-1,j=0),准备下一趟比较;

3.如果T中所有字符均比较完,则匹配成功,返回匹配的起始比较下标(i-j);否则匹配失败,返回-1;

代码实现如下

数据结构模式匹配——BF算法

设串S的长度为n,串T长度为m,在匹配成功的情况下,考虑两种极端情况。

(1)最好:不成功的匹配都发生在串T的第一个字符。

所有匹配成功的情况可能有n-m+1种

最坏情况:不成功的匹配都发生在串T的最后一个字符。

为什么BF算法的时间性能低?

在每趟匹配不成功时存在大量回溯,没有利用已经部分匹配的结果。

如何在匹配不成功的时候主串不回溯?

主串不回溯,模式就需要向右滑动一段距离。

因此KMP算法很好的解决这个问题