Python实现字符串匹配算法代码示例

yipeiwu_com7年前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 
  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编程实现蚁群算法详解

如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

相关文章

Python守护线程用法实例

本文实例讲述了Python守护线程用法。分享给大家供大家参考,具体如下: 如果你设置一个线程为守护线程,就表示你在说这个线程是不重要的,在进程退出的时候,不用等待这个线程退出。如果你的主...

Python中的面向对象编程详解(下)

继承 继承描述了基类的属性如何“遗传”给派生类。一个子类可以继承它的基类的任何属性,不管是数据属性还是方法。 创建子类的语法看起来与普通(新式)类没有区别,一个类名,后跟一个或多个需要...

python3+PyQt5实现支持多线程的页面索引器应用程序

python3+PyQt5实现支持多线程的页面索引器应用程序

本文通过Python3+pyqt5实现了python Qt GUI 快速编程的19章的页面索引器应用程序例子。 /home/yrd/eric_workspace/chap19/walke...

浅谈python中的数字类型与处理工具

浅谈python中的数字类型与处理工具

python中的数字类型工具 python中为更高级的工作提供很多高级数字编程支持和对象,其中数字类型的完整工具包括: 1.整数与浮点型, 2.复数, 3.固定精度十进制数, 4.有理分...

菜鸟使用python实现正则检测密码合法性

客户系统升级,要求用户密码符合一定的规则,即:包含大小写字母、数字、符号,长度不小于8,于是先用python写了个简单的测试程序: 在写解决方案前,列一下 python正则表达式中的特殊...