Python实现字符串匹配的KMP算法
作者:Goodspeed 发布时间:2021-02-10 05:03:45
标签:python,字符串,kmp
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算法网站的支持!
来源:https://www.cnblogs.com/goodspeed/p/3295456.html
0
投稿
猜你喜欢
- 前言本文的文字及图片来源于网络,仅供学习、交流使用,不具有任何商业用途,如有问题请及时联系我们以作处理基本开发环境 Python
- 大家好,我是安果!最近在部署前端项目的时候,需要先将前端项目压缩包通过堡垒机上传到应用服务器的 /tmp 目录下,然后进入应用服务器中,使用
- selenium3.0之后的版本的就不支持直接打开火狐浏览器,启动火狐浏览器报错,如下图,要想运行就需要我们单独装上驱动。3.0之前的版本,
- 开门见山自动化测试过程中,一般测试结果都会以邮件的形式发送给相关人员,那么,在Python中,如何编写代码将邮件发送给对应的用户?同时,发送
- 哪行哪业都少不了基本功,都说“马步”要扎得稳。在都快说烂了的以目标用户为中心设计的今天,还是要勤练基本功的。不多说了,先了解下“设计的3个C
- 在如今的Web设计中,图片的应用是必不可少的,为了更好地设计网站效果,大体积的图片被越来越多地应用到Web设计中来,所以,更好地优化图片文件
- 前言:最近碰到业务需要根据PSD文件实现PSD文件解析图层功能,搜到了Python的一个解析PSD的库。这个库就是psd-tools,psd
- 本章来实现一下删除已上传文件,同时优化了一下第一章中的代码。废话少说,上代码得意1.调整列表页面list.jsp<%@ page co
- PDO::rollBackPDO::rollBack — 回滚一个事务(PHP 5 >= 5.1.0, PECL pdo >=
- 很多朋友都有过制作网页的经历,如今,众多网页的设计都用到了表格。这样不仅有利于网页的维护,同时,提高了网页的观赏性。在众多网页制作风格中,细
- 一、configparser模块是什么可以用来操作后缀为 .ini 的配置文件;python标准库(就是python自带的意思,无需安装)二
- 本文介绍了在Python中使用gRPC的方法示例,分享给大家,具体如下:使用Protocol Buffers的跨平台RPC系统。安装使用 p
- 本文通过Python3+PyQt5实现自定义部件–Counters自定 窗口部件。这个窗口是3*3的网格。本文有两个例子如下: /home/
- PyMongo是什么PyMongo是驱动程序,使python程序能够使用Mongodb数据库,使用python编写而成.安装环境
- 后台数据库用是Access,客户用了一年后说打开界面非常慢,查看了数据库后发现数据表中的记录已有五万多条,自己试过将记录复制到10 万条,打
- 本文主要介绍了Matlab中plot基本用法的具体使用,分享给大家,具体如下:>> y=[0 0.58 0.70 0.95 0.
- 学习使用存储过程(Stored Procedure),是ASP程序员的必须课之一。所有的大型数据库都支持存储过程,比如Oracle
- 通常来说,一个Python程序可以从键盘读取输入,也可以从文件读取输入;而程序的结果可以输出到屏幕上,也可以保存到文件中便于以后使用。本文就
- Python包导入报错的问题首先,一般来说,写一个小demo可能一个文件就够了,但是要是做一个小项目,可能需要拆分成很多零散的文件,放在不同
- //-------------------------------------------- // 删除千分点。 //-----------