首页 > 代码库 > B-F 字符串匹配算法

B-F 字符串匹配算法

Brute-Froce 算法是串的匹配模式算法中的一种
其匹配方式如下:
1、设有字符串 a ,b;a为主串,在 a 中查找 b 串的位置
2、匹配方式如下:
2.1:
分别从 a,b串的第一个元素开始比较a,b 中每个元素是否相等。如果相等,那么比较a,b各自的下一个元素。直到a,b中出现了某个元素不相等(或者是a或者b中所有的元素都比较了一个遍,这种情况一会说)。那么:
2.2:
从a中的第二个字符和b中的第一个字符开始比较,看是否相等,如果相等,那么顺序比较a,b中各自后面的元素。直到出现了不相等(或者是a或者b中所有的元素都比较了一个遍,这种情况一会说):
2.3:
重复2.2,从a中的第三个开始和b中的第一个元素开始比较。。。。。。直到出现了不相等。

一直重复以上过程,直到:
3.1 b中所有元素都比较完了:
这说明,找到了b在a中的位置
3.2 a中所有的元素都比较完了:
这说明,a中不含有b


图示如下:

开始查找

技术分享

 

a[i] != b[j] 出现了不匹配的元素

 

从a 的第二个元素开始和b的第一个元素开始匹配

 技术分享

 

 

a[i]  != b[j]

从a的第三个元素开始和b的第一个元素开始匹配

技术分享

 

 

 

多图之后就会发现,如果出现不匹配,那么那么它们的初始匹配位置就在 a[i-j] 而下一次匹配 就从  a[i-j+1] 开始匹配 b[0] 然后依次匹配下去。。。。。

直到  a全部匹配完:

技术分享

 

或者是 b 全部匹配完:

技术分享

 

 代码如下:

 

 

#coding:utf-8

a = input("a  >")
b = input("b  >")

a_len = len(a)
b_len = len(b)


i = 0
j = 0

while(i < a_len and j < b_len):  # i,j 为索引,所以不可能等于a,b的长度
    
    if a[i] == b[j]:
        i += 1      # 如果两个元素相等,那么就匹配下一个元素
        j += 1
    else:
        i = i-j+1   # a 从 第 i-j+1 的位置开始重新匹配
        j = 0       # b 依旧从 0 开始匹配


if i>=a_len: # 说明 a 已经全部匹配了。仍未找到b
    print(a字符串中不含有b字符串)
else:  # 说明退出while循环条件为  j>=b_len更具体来说是 j=b_len  ,已经把b找完了。说明a中含有b,
    site = i - j # 所以他们的最后一次匹配的开始位置就是  i - j
    print(a中含有b.且初始匹配位置为 %d,匹配长度为 %d % (site, j))

 

 

 

 

 

B-F 字符串匹配算法