Python實(shí)現(xiàn)字符串匹配的KMP算法

更新時(shí)間：2019年04月04日 10:46:18 作者：Goodspeed

KMP算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。這篇文章主要介紹了Python實(shí)現(xiàn)字符串匹配的KMP算法,需要的朋友可以參考下

kmp算法

KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)，因此人們稱(chēng)它為克努特——莫里斯——普拉特操作（簡(jiǎn)稱(chēng)KMP算法）。KMP算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。具體實(shí)現(xiàn)就是實(shí)現(xiàn)一個(gè)next()函數(shù)，函數(shù)本身包含了模式串的局部匹配信息。

#! /usr/bin/python
# coding=utf-8
"""
基于這篇文章的python實(shí)現(xiàn)
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
    #移動(dòng)位數(shù) = 已匹配的字符數(shù) – 對(duì)應(yīng)的部分匹配值
    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()

總結(jié)

以上所述是小編給大家介紹的Python實(shí)現(xiàn)字符串匹配的KMP算法，希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！

您可能感興趣的文章:

相關(guān)文章

Python序列化pickle模塊使用詳解
這篇文章主要介紹了Python序列化pickle模塊使用詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2020-03-03
python中類(lèi)的相互調(diào)用的實(shí)踐
本文主要介紹了python中類(lèi)的相互調(diào)用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2023-02-02
python做http代理請(qǐng)求的項(xiàng)目實(shí)踐
本文主要介紹了使用Python Flask實(shí)現(xiàn)HTTP代理服務(wù)器的解決方案,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2025-03-03
Numpy?三維數(shù)組索引與切片的實(shí)現(xiàn)
本文主要介紹了Numpy?三維數(shù)組索引與切片，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2023-03-03
如何使用yolov5輸出檢測(cè)到的目標(biāo)坐標(biāo)信息
YOLOv5是一系列在 COCO 數(shù)據(jù)集上預(yù)訓(xùn)練的對(duì)象檢測(cè)架構(gòu)和模型,下面這篇文章主要給大家介紹了關(guān)于如何使用yolov5輸出檢測(cè)到的目標(biāo)坐標(biāo)信息的相關(guān)資料,需要的朋友可以參考下
2022-03-03
對(duì)python中Librosa的mfcc步驟詳解
今天小編就為大家分享一篇對(duì)python中Librosa的mfcc步驟詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
2019-01-01
如何在python中實(shí)現(xiàn)ECDSA你知道嗎
這篇文章主要為大家介紹了python中實(shí)現(xiàn)ECDSA，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助，希望能夠給你帶來(lái)幫助
2021-11-11
python錯(cuò)誤：AttributeError: ''module'' object has no attribute
這篇文章主要介紹了python錯(cuò)誤：AttributeError: 'module' object has no attribute 'setdefaultencoding'問(wèn)題的解決方法,需要的朋友可以參考下
2014-08-08
Django ORM實(shí)現(xiàn)按天獲取數(shù)據(jù)去重求和例子
這篇文章主要介紹了Django ORM實(shí)現(xiàn)按天獲取數(shù)據(jù)去重求和例子，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
2020-05-05
Python函數(shù)默認(rèn)參數(shù)常見(jiàn)問(wèn)題及解決方案
這篇文章主要介紹了Python函數(shù)默認(rèn)參數(shù)常見(jiàn)問(wèn)題及解決方案,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2020-03-03