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

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

赞 (0)

相关推荐

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

    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

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

    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算法之图的遍历

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

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

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

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

  • Python实现调度算法代码详解

    Python实现调度算法代码详解

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

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

    字符串匹配存在的问题 Python中在一个长字符串中查找子串是否存在可以用两种方法:一是str的find()函数,find()函数只返回子串匹配到的起始位置,若没有,则返回-1:二是re模块的findall函数,可以返回所有匹配到的子串. 但是如果用findall函数时需要注意字符串中存在的特殊字符 蛮力法字符串匹配: 将模式对准文本的前m(模式长度)个字符,然后从左到右匹配每一对对应的字符,直到全部匹配或遇到一个不匹配的字符.后一种情况下,模式向右移一位. 代码如下: def string_m

  • python实现机械分词之逆向最大匹配算法代码示例

    python实现机械分词之逆向最大匹配算法代码示例

    逆向最大匹配方法 有正即有负,正向最大匹配算法大家可以参阅http://www.jb51.net/article/127404.htm 逆向最大匹配分词是中文分词基本算法之一,因为是机械切分,所以它也有分词速度快的优点,且逆向最大匹配分词比起正向最大匹配分词更符合人们的语言习惯.逆向最大匹配分词需要在已有词典的基础上,从被处理文档的末端开始匹配扫描,每次取最末端的i个字符(分词所确定的阈值i)作为匹配字段,若匹配失败,则去掉匹配字段最前面的一个字,继续匹配.而且选择的阈值越大,分词越慢,但准确性

  • Python中字符串与编码示例代码

    在最新的Python 3版本中,字符串是以Unicode编码的,即Python的字符串支持多语言 编码和解码 字符串在内存中以Unicode表示,在操作字符串时,经常需要str和bytes互相转换   如果在网络上传输或保存到磁盘上,则从内存读到的数据就是str,要把str变为以字节为单位的bytes,称为编码   如果从网络或磁盘上读取字节流,则从网络或磁盘上读到的数据就是bytes,要把bytes变为str,称为解码   为避免乱码问题,应当始终坚持使用UTF-8编码对str和bytes进行

  • Java调用JavaScript实现字符串计算器代码示例

    如果表达式是字符串的形式,那么一般我们求值都会遇到很大的问题. 这里有一种直接调用JavaScript的方法来返回数值,无疑神器. 代码如下: package scc; import javax.script.ScriptEngine; import javax.script.ScriptEngineManager; import javax.script.ScriptException; public class Counter { public static void main(String

  • Python多线程扫描端口代码示例

    本文代码实现Python多线程扫描端口,具体实现代码如下. #coding:utf-8 import socket import thread import time socket.setdefaulttimeout(3) def socket_port(ip,port): try: if port>=65535: print(u"端口扫描结束!") s=socket.socket(socket.AF_INET,socket.SOCK_STREAM)#创建套接字 result=s

  • python删除服务器文件代码示例

    python删除服务器文件代码示例

    本文主要研究的是Python编程删除服务器文件,具体实现 代码如下. 实例1 #coding:utf-8 import paramiko """ 创建文件 删除文件 root权限 """ ssh=paramiko.SSHClient() ssh.set_missing_host_key_policy(paramiko.AutoAddPolicy()) ssh.connect(hostname="192.168.1.37",po

  • Python语言生成水仙花数代码示例

    Python语言生成水仙花数代码示例

    水仙花数是指一个 n 位数 ( n≥3 ),它的每个位上的数字的 n 次幂之和等于它本身. 本文将通过Python代码实现打印水仙花数,具体如下: #水仙花数 #narcissistic number #水仙花数是指一个 n 位数 ( n≥3 ),它的每个位上的数字的 n 次幂之和等于它本身. #(例如:1^3 + 5^3+ 3^3 = 153) import math import string for x in range(1,10): a=x*x*x for y in range(0,10

  • python使用邻接矩阵构造图代码示例

    问题 如何使用list构造图 邻接矩阵的方式 Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 # 邻接矩阵 ''' a---b\ | | \ | | c | | / e---d/ 对于无向图顶点之间存在边,则为1,反之则为0 a b c d e a 0 1 0 0 1 b 1 0 1 1 0 c 0 1 0 1 0 d 0 1 1 0 1 e 1 0 0 1 0 观

  • Python求字符串的长度示例代码

    目录 Python求字符串的长度 补充:Python计算字符串长度的函数 Python三种计算字符串长度的函数 1.使用内置函数len 2.使用for循环 3.使用while循环和切片 Python求字符串的长度 python 写一个函数,求一个字符串的长度,在main函数中输入字符串,并输出其长度. def func(a): #定义一个求字符串长度的函数 '求一个字符串的长度' len=0 for i in a: len+=1 return len if __name__=='__main__

  • python切换hosts文件代码示例

    win7以上需要使用管理员权限操作. 复制代码 代码如下: # -*- coding: utf-8 -*-import osimport globimport shutil def format_file_list(files):        all_files_str = ""        for i in range(len(files)):                all_files_str +=  str(i)+":"+files[i]+"

随机推荐