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

Ivy

发布时间：2026-10-13| 4人浏览过

原创

本文介绍KMP字符串匹配算法的原理及Python实现。KMP通过next数组（部分匹配表）避免回溯，提高匹配效率。文章包含核心代码解析、部分匹配值计算逻辑及单元测试示例，帮助开发者理解并应用该算法。

KMP算法概述

KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth、J.H.Morris和V.R.Pratt共同发现，因此得名克努特-莫里斯-普拉特算法（简称KMP）。该算法的核心在于利用匹配失败后的信息，尽量减少模式串与主串的重复比对次数，从而实现快速匹配。具体实现中，关键在于构建一个next()函数，该函数记录了模式串的局部匹配信息，用于指导后续匹配位置。

Python代码实现


#! /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()