做钓鱼网站用哪种编程语言,百度h5发布,狼雨seo培训,怎么做招投标网站字符串匹配存在的问题
Python中在一个长字符串中查找子串是否存在可以用两种方法#xff1a;一是str的find()函数#xff0c;find()函数只返回子串匹配到的起始位置#xff0c;若没有#xff0c;则返回-1#xff1b;二是re模块的findall函数#xff0c;可以返回所有匹配到…字符串匹配存在的问题
Python中在一个长字符串中查找子串是否存在可以用两种方法一是str的find()函数find()函数只返回子串匹配到的起始位置若没有则返回-1二是re模块的findall函数可以返回所有匹配到的子串。
但是如果用findall函数时需要注意字符串中存在的特殊字符
蛮力法字符串匹配
将模式对准文本的前m模式长度个字符然后从左到右匹配每一对对应的字符直到全部匹配或遇到一个不匹配的字符。后一种情况下模式向右移一位。
代码如下
def string_match(string, sub_str): # 蛮力法字符串匹配 for i in range(len(string)-len(sub_str)
1): index i #
index指向下一个待比较的字符 for j in
range(len(sub_str)): if string[index]
sub_str[j]: index
1
else: break
if index-i
len(sub_str): return
i return -1
if __name__ __main__: print(string_match(adbcbdc, dc))
最坏情况下该算法属于Θ(nm)事实上该算法的平均效率比最差效率好得多。事实上在查找随机文本的时候其属于线性的效率Θ(n)。
Horspool算法
Horsepool算法是Boyer-Moore算法的简化版本这也是一个空间换时间的典型例子。算法把模式P和文本T的开头字符对齐从模式的最后一个字符开始比较如果尝试比较失败了它把模式向后移。每次尝试过程中比较是从右到左的。
在蛮力算法中模式的每一次移动都是一个字符Horspool算法的核心思想是利用空间来换取时间提升模式匹配窗口的移动幅度。与蛮力算法不同的是其模式的匹配是从右到左的通过预先算出每次移动的距离并存于表中。
代码如下 __author__ Wang
from collections import defaultdict def shift_table(pattern): # 生成 Horspool 算法的移动表 # 当前检测字符为c模式长度为m #
如果当前c不包含在模式的前m-1个字符中移动模式的长度m #
其他情况下移动最右边的的c到模式最后一个字符的距离 table defaultdict(lambda:
len(pattern)) for index in range(0,
len(pattern)-1): table[pattern[index]] len(pattern) - 1 -
index return table def horspool_match(pattern, text): # 实现 horspool 字符串匹配算法 # 匹配成功返回模式在text中的开始部分否则返回
-1 table
shift_table(pattern) index len(pattern) - 1
while index len(text) -
1: print(start matching at,
index) match_count 0
while match_count len(pattern)
and pattern[len(pattern)-1-match_count]
text[index-match_count]: match_count 1
if match_count
len(pattern): return index-match_count
1
else: index
table[text[index]] return -1
if __name__ __main__: print(horspool_match(barber,
jim_saw_me_in_a_barbershopp))
显然Horspool算法的最差效率属于属于Θ(nm)。在查找随机文本的时候其属于线性的效率Θ(n)。虽然效率类型相同但平均来说Horspool算法比蛮力算法快很多。
