Python实现字符串匹配算法代码示例
本文介绍在Python中实现字符串匹配的两种常用方法：内置的find()与re.findall()，以及算法层面的蛮力法和Horspool算法。详细解析了蛮力法的时间复杂度及Horspool算法通过空间换时间优化匹配窗口的原理，并提供了完整的Python代码示例与性能分析。
字符串匹配存在的问题
在Python中，若需判断长字符串内是否包含特定子串，通常有两种基础方式：一是使用字符串对象的find()方法，该方法仅返回子串首次出现的起始索引，若未找到则返回-1；二是利用re模块的findall()函数，该函数能够返回所有匹配到的子串列表。
然而，在使用findall()函数时，必须注意处理字符串中可能存在的特殊字符，以免正则表达式解析出现意外结果。
蛮力法字符串匹配：
该方法将模式串与文本串的前m个字符（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为文本长度，m为模式长度。实际上，该算法的平均效率远优于最坏情况。特别是在处理随机文本时，其平均时间复杂度可接近线性效率Θ(n)。
Horspool算法：
Horspool算法是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算法的平均速度显著快于蛮力算法。
总结
以上就是本文关于Python实现字符串匹配算法代码示例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站：
Python实现调度算法代码详解
Python算法之图的遍历
Python编程实现蚁群算法详解
如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
