欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-11-16 16:34:46
kmp算法 kmp算法是一种改进的字符串匹配算法,由d.e.knuth,j.h.morris和v.r.pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简...

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算法,希望对大家有所帮助