Python实现字符串匹配的KMP算法

2024-12-21 16:54:58

kmp算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。

#! /usr/bin/python
# coding=utf-8
"""
基于这篇文章的python实现
http://blog.sae.sina.com.cn/archives/307
"""
import unittest
def pmt(s):
  """
  PartialMatchTable
  """
  prefix = [s[:i+1] for i in range(len(s)-1)]
  postfix = [s[i+1:] for i in range(len(s)-1)]
  intersection = list(set(prefix) & set(postfix))
  if intersection:
    return len(intersection[0])
  return 0
def kmp(big,small):
  i = 0
  while i < len(big) - len(small) + 1:
    match = True
    for j in range(len(small)):
      if big[i+j] != small[j]:
        match = False
        break
    if match:
      return True
    #移动位数 = 已匹配的字符数 – 对应的部分匹配值
    if j:
      i += j - pmt(small[:j])
    else:
      i += 1
  return False
class kmpTests(unittest.TestCase):
  def test_pmt(self):
    self.assertEqual(pmt("A"),0)
    self.assertEqual(pmt("AB"),0)
    self.assertEqual(pmt("ABC"),0)
    self.assertEqual(pmt("ABCD"),0)
    self.assertEqual(pmt("ABCDA"),1)
    self.assertEqual(pmt("ABCDAB"),2)
    self.assertEqual(pmt("ABCDABD"),0)
    self.assertEqual(pmt("AAAAAA"),5)
  def test_kmp(self):
    self.assertTrue(kmp("ABCD","CD"))
    self.assertFalse(kmp("ABCD","BD"))
    self.assertTrue(kmp("BBC ABCDAB ABCDABCDABDE","ABCDABD"))
if __name__ == '__main__':
  unittest.main()

总结

以上所述是小编给大家介绍的Python实现字符串匹配的KMP算法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

详解python多线程之间的同步(一)

引言: 线程之间经常需要协同工作,通过某种技术,让一个线程访问某些数据时,其它线程不能访问这些数据,直到该线程完成对数据的操作.这些技术包括临界区(Critical Section),互斥量(Mutex),信号量(Semaphore),事件Event等. Event threading库中的event对象通过使用内部一个flag标记,通过flag的True或者False的变化来进行操作. 名称含义 set( )
详解python项目实战:模拟登陆CSDN

前言今天为大家介绍一个利用Python模拟登陆CSDN的案例,虽然看起来很鸡肋,有时候确会有大用处,在这里就当做是一个案例练习吧,提高自己的代码水平,也了解Python如何做到模拟登陆的, 下面来看代码导入库获取头部信息解析网页返回登录过后的session 检测是否登陆正常运行结果以上所述是小编给大家介绍的python项目实战:模拟登陆CSDN详解整合,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的.在此也非常感谢大家对我们网站的支持!
详解python读取image

python 读取image 在python中我们有两个库可以处理图像文件,scipy和matplotlib. 安装库 pip install matplotlib pillow scipy 用法 from scipy.misc import imread data = imread(image_root) #data是 ndarray对象 import matplotlib.image as mpimg data = mpimg.imread(image_root) #data是 ndarra
Python GUI编程完整示例

本文实例讲述了Python GUI编程.分享给大家供大家参考,具体如下: import os from time import sleep from tkinter import * from tkinter.messagebox import showinfo class DirList(object): def __init__(self, initdir=None): self.top = Tk() self.label = Label(master=self.top, text='Dir
python dlib人脸识别代码实例

本文实例为大家分享了python dlib人脸识别的具体代码,供大家参考,具体内容如下 import matplotlib.pyplot as plt import dlib import numpy as np import glob import re #正脸检测器 detector=dlib.get_frontal_face_detector() #脸部关键形态检测器 sp=dlib.shape_predictor(r"D:\LB\JAVASCRIPT\shape_predictor_68
python实现kmp算法的实例代码

kmp算法 kmp算法用于字符串的模式匹配,也就是找到模式字符串在目标字符串的第一次出现的位置比如 abababc 那么bab在其位置1处,bc在其位置5处我们首先想到的最简单的办法就是蛮力的一个字符一个字符的匹配,但那样的时间复杂度会是O(m*n) kmp算法保证了时间复杂度为O(m+n) 基本原理举个例子: 发现x与c不同后,进行移动 a与x不同,再次移动此时比较到了c与y, 于是下一步移动成了下面这样这一次的移动与前两次的移动不同,之前每次比较到上面长字符串的字符位置后,直接把模
详解Python的数据库操作（pymysql）

使用原生SQL语句进行对数据库操作,可完成数据库表的建立和删除,及数据表内容的增删改查操作等.其可操作性很强,如可以直接使用"show databases"."show tables"等语句进行表格之外的部分操作. Centos7远程操作数据库时需要关闭防火墙,否则会连接不上安装: pip3 install pymysql 数据查询: import pymysql #建立数据库连接 conn=pymysql.connect(host="192.168.1
Python选择网卡发包及接收数据包

当一台计算机上有多个网卡时,需要选择对应IP地址的网卡进行发送数据包或者接受数据包. 1.选择网卡发包(应用scapy): plface=conf.route.route("××.××.××.××")[0] #××.××.××.××为对应网卡网络中存在设备的IP地址.不能是需要发送数据包的网卡的IP地址(会报"result too large") pkt=conf.L2socket(plface) pack_ip,pack_udp,pack_ether=self.u
Python将列表数据写入文件（txt, csv，excel）

写入txt文件 def text_save(filename, data):#filename为写入CSV文件的路径,data为要写入数据列表. file = open(filename,'a') for i in range(len(data)): s = str(data[i]).replace('[','').replace(']','')#去除[],这两行按数据不同,可以选择 s = s.replace("'",'').replace(',','') +'\n' #去除单引号,
python爬虫简单的添加代理进行访问的实现代码

在使用python对网页进行多次快速爬取的时候,访问次数过于频繁,服务器不会考虑User-Agent的信息,会直接把你视为爬虫,从而过滤掉,拒绝你的访问,在这种时候就需要设置代理,我们可以给proxies属性设置一个代理的IP地址,代码如下: import requests from lxml import etree url = "https://www.ip.cn" headers = {"User-Agent": "Mozilla/5.0 (Wind

Python实现字符串匹配的KMP算法

相关推荐

随机推荐