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

yipeiwu_com7年前Python基础

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设计】网站的支持!

相关文章

Python设置Socket代理及实现远程摄像头控制的例子

为python设置socket代理 首先,你得下载SocksiPy这个.解压出来之后里面会有一个socks.py文件.然后你可以把这个文件复制到python安装目录里面的Lib\site...

Python中让MySQL查询结果返回字典类型的方法

Python的MySQLdb模块是Python连接MySQL的一个模块,默认查询结果返回是tuple类型,只能通过0,1..等索引下标访问数据 默认连接数据库: 复制代码 代码如下: M...

python使用Matplotlib画条形图

python使用Matplotlib画条形图

本文实例为大家分享了python使用Matplotlib画条形图的具体代码,供大家参考,具体内容如下 数据 中国的四个直辖市分别为北京市、上海市、天津市和重庆市,其2017年上半年的G...

Python OpenCV 使用滑动条来调整函数参数的方法

Python OpenCV 使用滑动条来调整函数参数的方法

引言 在观察OpenCV中某个函数在不同参数的情况下,所得到的效果的时候,我之前是改一次参数运行一次,这样做起来操作麻烦,效率低下。为了更便捷的观察参数变化时带来的处理效果改变 可以使用...

spyder常用快捷键(分享)

最近在学习tensorflow框架,在ubuntu下用到python的一个ide --spyder,以下是常用快捷键 Ctrl+1:注释/撤销注释 Ctrl+4/5:块注释/撤销块注释...