python数据分析实例代码-Python实现字符串匹配算法代码⽰
例
字符串匹配存在的问题
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
python新手代码示例
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算法⽐蛮⼒算法快很多。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。