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

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

相关文章

Django实现发送邮件找回密码功能

Django实现发送邮件找回密码功能

在各大网站上,一定都遇到过找回密码的问题,通常采用的方式是通过发送带有验证码的邮件进行身份验证,本文将介绍通过Django实现邮件找回密码功能。 找回密码流程 功能流程: 1.首先在用户...

Python访问MongoDB,并且转换成Dataframe的方法

如下所示: #!/usr/bin/env python # -*- coding: utf-8 -*- # @Time : 2018/7/13 11:10 # @Author : b...

Python解析excel文件存入sqlite数据库的方法

一、建立数据库 根据需求建立数据库,建立了两个表,并保证了可以将数据存储到已有的数据库中,代码如下: import sqlite3 def createDataBase(): cn...

请不要重复犯我在学习Python和Linux系统上的错误

请不要重复犯我在学习Python和Linux系统上的错误

本人已经在运维行业工作了将近十年,我最早接触Linux是在大二的样子,那时候只追求易懂,所以就选择了Ubuntu作为学习、使用的对象,它简单、易用、好操作、界面绚丽,对于想接触Linux...

Python中的变量和作用域详解

作用域介绍 python中的作用域分4种情况: L:local,局部作用域,即函数中定义的变量; E:enclosing,嵌套的父级函数的局部作用域,即包含此函数的上级函数的局部作用域...