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

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

时间: 2017-12-03

Python算法之图的遍历

本节主要介绍图的遍历算法BFS和DFS,以及寻找图的(强)连通分量的算法 Traversal就是遍历,主要是对图的遍历,也就是遍历图中的每个节点.对一个节点的遍历有两个阶段,首先是发现(discover),然后是访问(visit).遍历的重要性自然不必说,图中有几个算法和遍历没有关系?! [算法导论对于发现和访问区别的非常明显,对图的算法讲解地特别好,在遍历节点的时候给节点标注它的发现节点时间d[v]和结束访问时间f[v],然后由这些时间的一些规律得到了不少实用的定理,本节后面介绍了部分内容,感

Python2.7基于笛卡尔积算法实现N个数组的排列组合运算示例

本文实例讲述了Python2.7基于笛卡尔积算法实现N个数组的排列组合运算.分享给大家供大家参考,具体如下: 说明:本人前段时间遇到的求n个数组的所有排列组合的问题,发现笛卡尔积算法可以解决,但是网上搜索的只有Java版本的实现,于是自己试着用python实现,由于新手代码不太规范. 代码:本人封装了一个类Cartesian(笛卡尔),其中封装了变量和方法: 1.变量 datagroup : 表示n个list(python 中的list与其他编程中的数组定义类似)的集合,即一个二维数组 coun

Python基于贪心算法解决背包问题示例

本文实例讲述了Python基于贪心算法解决背包问题.分享给大家供大家参考,具体如下: 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解. 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关. 完全背包问题:给定n个物品和一个容量为C的背包,物品i的重量是Wi,其价值为Vi,背包问题是如何选择入背包

Python实现的归并排序算法示例

本文实例讲述了Python实现的归并排序算法.分享给大家供大家参考,具体如下: 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. Python实现代码如下: #-*- coding: UTF-8 -*- import numpy as np def Merge(a, f, m, l):

TF-IDF算法解析与Python实现方法详解

TF-IDF(term frequency–inverse document frequency)是一种用于信息检索(information retrieval)与文本挖掘(text mining)的常用加权技术.比较容易理解的一个应用场景是当我们手头有一些文章时,我们希望计算机能够自动地进行关键词提取.而TF-IDF就是可以帮我们完成这项任务的一种统计方法.它能够用于评估一个词语对于一个文集或一个语料库中的其中一份文档的重要程度. 在一份给定的文件里,词频 (term frequency, T

Python字符串匹配算法KMP实例

本文实例讲述了Python字符串匹配算法KMP.分享给大家供大家参考.具体如下: #!/usr/bin/env python #encoding:utf8 def next(pattern): p_len = len(pattern) pos = [-1]*p_len j = -1 for i in range(1, p_len): while j > -1 and pattern[j+1] != pattern[i]: j = pos[j] if pattern[j+1] == pattern

Python实现调度算法代码详解

调度算法 操作系统管理了系统的有限资源,当有多个进程(或多个进程发出的请求)要使用这些资源时,因为资源的有限性,必须按照一定的原则选择进程(请求)来占用资源.这就是调度.目的是控制资源使用者的数量,选取资源使用者许可占用资源或占用资源. 在操作系统中调度是指一种资源分配,因而调度算法是指:根据系统的资源分配策略所规定的资源分配算法.对于不同的的系统和系统目标,通常采用不同的调度算法,例如,在批处理系统中,为了照顾为数众多的段作业,应采用短作业优先的调度算法:又如在分时系统中,为了保证系统具有合理

Python探索之ModelForm代码详解

这是一个神奇的组件,通过名字我们可以看出来,这个组件的功能就是把model和form组合起来,对,你没猜错,相信自己的英语水平. 先来一个简单的例子来看一下这个东西怎么用: 比如我们的数据库中有这样一张学生表,字段有姓名,年龄,爱好,邮箱,电话,住址,注册时间等等一大堆信息,现在让你写一个创建学生的页面,你的后台应该怎么写呢? 首先我们会在前端一个一个罗列出这些字段,让用户去填写,然后我们从后天一个一个接收用户的输入,创建一个新的学生对象,保存 其实,重点不是这些,而是合法性验证,我们需要在前端

MySQL数据库设计之利用Python操作Schema方法详解

弓在箭要射出之前,低声对箭说道,"你的自由是我的".Schema如箭,弓似Python,选择Python,是Schema最大的自由.而自由应是一个能使自己变得更好的机会. Schema是什么? 不管我们做什么应用,只要和用户输入打交道,就有一个原则--永远不要相信用户的输入数据.意味着我们要对用户输入进行严格的验证,web开发时一般输入数据都以JSON形式发送到后端API,API要对输入数据做验证.一般我都是加很多判断,各种if,导致代码很丑陋,能不能有一种方式比较优雅的验证用户数据呢

python学习 流程控制语句详解

###################### 分支语句 python3.5 ################ #代码的缩进格式很重要 建议4个空格来控制 #根据逻辑值(True,Flase)判断程序的运行方向 # Ture:表示非空的量(String,tuple元组 .list.set.dictonary),所有非零的数字 # False:0,None .空的量 #逻辑表达式 可以包含 逻辑运算符 and or not if: ##################################

Python 调用Java实例详解

Python 调用Java实例详解 前言: Python 对服务器端编程不如Java 所以这方面可能要调用Java代码 前提: Linux 环境  1 安装 jpype1 安装后测试代码: from jpype import * startJVM(getDefaultJVMPath(), "-ea") java.lang.System.out.println("Hello World") shutdownJVM() 2 调用非jdk的jar包, test.jar 包

python 编程之twisted详解及简单实例

python 编程之twisted详解 前言: 我不擅长写socket代码.一是用c写起来比较麻烦,二是自己平时也没有这方面的需求.等到自己真正想了解的时候,才发现自己在这方面确实有需要改进的地方.最近由于项目的原因需要写一些Python代码,才发现在python下面开发socket是一件多么爽的事情. 对于大多数socket来说,用户其实只要关注三个事件就可以了.这分别是创建.删除.和收发数据.python中的twisted库正好可以帮助我们完成这么一个目标,实用起来也不麻烦.下面的代码来自t

Python 文件操作的详解及实例

Python 文件操作的详解及实例 一.文件操作 1.对文件操作流程 打开文件,得到文件句柄并赋值给一个变量 通过句柄对文件进行操作 关闭文件 现有文件如下: 昨夜寒蛩不住鸣. 惊回千里梦,已三更. 起来独自绕阶行. 人悄悄,帘外月胧明. 白首为功名,旧山松竹老,阻归程. 欲将心事付瑶琴. 知音少,弦断有谁听. f = open('小重山') #打开文件 data=f.read()#获取文件内容 f.close() #关闭文件 注意:if in the win,hello文件是utf8保存的,打

Python的语言类型(详解)

Python 是强类型的动态脚本语言 . 强类型:不允许不同类型相加 动态:不使用显示数据类型声明,且确定一个变量的类型是在第一次给它赋值的时候 脚本语言:一般也是解释型语言,运行代码只需要一个解释器,不需要编译 强类型语言和弱类型语言 1.强类型语言:使之强制数据类型定义的语言.没有强制类型转化前,不允许两种不同类型的变量相互操作.强类型定义语言是类型安全的语言,如Java.C# 和 python,比如Java中"int i = 0.0;"是无法通过编译的: 2.弱类型语言:数据类型

Python缩进和冒号详解

对于Python而言代码缩进是一种语法,Python没有像其他语言一样采用{}或者begin...end分隔代码块,而是采用代码缩进和冒号来区分代码之间的层次. 缩进的空白数量是可变的,但是所有代码块语句必须包含相同的缩进空白数量,这个必须严格执行. 例如: if True: print("Hello girl!") #缩进一个tab的占位 else: #与if对齐 print("Hello boy!") #缩进一个tab的占位 Python对代码的缩进要求非常严格

基于Python闭包及其作用域详解

关于Python作用域的知识在python作用域有相应的笔记,这个笔记是关于Python闭包及其作用域的详细的笔记 如果在一个内部函数里,对一个外部作用域(但不是全局作用域)的变量进行引用,那么内部函数就被称为闭包(closure),而这个被内部函数引用的变量则被成为自由变量 闭包和函数调用没多少相关,而是关于使用定义在其他作用域的变量 命名空间和作用域 我们把命名空间看做一个大型的字典类型(Dict),里面包含了所有变量的名字和值的映射关系.在 Python 中,作用域实际上可以看做是"在当前

python 系统调用的实例详解

python 系统调用的实例详解               本文将通过两种方法对python 系统调用进行讲解,包括python使用CreateProcess函数运行其他程序和ctypes模块的实例, 一 python使用CreateProcess函数运行其他程序 >>> import win32process >>> handle = win32process.CreateProcess('c:\\windows\\notepad.exe','',None,None