简单!
全部博文(366)
分类: C/C++
2013-04-25 23:48:19
一、BF算法
BF算法是普通的模式匹配算法,其基本思想就是将目标串的第一个字符与模式串的第一个字符进行匹配。若相等,则继续比较第二个字符;若不相等,则比较目标串的第二个字符和模式串的第一个字符。依次比较下去,直到得出最后的匹配结果。
示例代码:
例如我们要在"substring searching"查找"search",刚开始时,把子串与文本左边对齐:
s |
u |
b |
s |
t |
r |
i |
n |
g |
|
s |
e |
a |
r |
c |
h |
i |
n |
g |
s |
e |
a |
r |
c |
h |
|
|
|
|
|
|
|
|
|
|
|
|
|
结果在第二个字符处发现不匹配,于是要把子串往后移动。但是该移动多少呢?这就是各种算法各显神通的地方了,最简单的做法是移动一个字符位置;KMP是利用已经匹配部分的信息来移动;BM算法是做反向比较,并根据已经匹配的部分来确定移动量。这里要介绍的方法是看紧跟在当前子串之后的那个字符(上图中的'i')。
显然,不管移动多少,这个字符是肯定要参加下一步的比较的,也就是说,如果下一步匹配到了,这个字符必须在子串内。所以,可以移动子串,使子串中的最右边的这个字符与它对齐。现在子串'search'中并不存在'i',则说明可以直接跳过一大片,从'i'之后的那个字符开始作下一步的比较,如下图:
s |
u |
b |
s |
t |
r |
i |
n |
g |
|
s |
e |
a |
r |
c |
h |
i |
n |
g |
|
|
|
|
|
|
|
s |
e |
a |
r |
c |
h |
|
|
|
|
|
|
比较的结果,第一个字符就不匹配,再看子串后面的那个字符是'r',它在子串中出现在倒数第三位,于是把子串向前移动三位,使两个'r'对齐,如下:
s |
u |
b |
s |
t |
r |
i |
n |
g |
|
s |
e |
a |
r |
c |
h |
i |
n |
g |
|
|
|
|
|
|
|
|
|
|
s |
e |
a |
r |
c |
h |
|
|
|
这次匹配成功了!回顾整个过程,我们只移动了两次子串就找到了匹配位置。可以证明:用这个算法,每一步的移动量都比BM算法要大,所以肯定比BM算法更快。
以上Sunday算法文字描述摘自 这里。
代码实现: