首页 > 代码库 > 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 字符串匹配算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。