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)，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱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ì)大家有所幫助，如果大家有任何疑問請給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
相關(guān)文章
在交互式環(huán)境中執(zhí)行Python程序過程詳解
這篇文章主要介紹了在交互式環(huán)境中執(zhí)行Python程序過程詳解，運(yùn)行Python腳本程序的方式有多種，目前主要的方式有：交互式環(huán)境運(yùn)行、命令行窗口運(yùn)行、開發(fā)工具上運(yùn)行等，其中在不同的操作平臺(tái)上還互不相同,需要的朋友可以參考下2019-07-07
這篇文章主要為大家介紹了Python基本數(shù)據(jù)類型，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
這篇文章主要介紹了python以環(huán)狀形式組合排列圖片并輸出的方法,涉及Python使用pil庫操作圖片的技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-03-03
Restful_framework視圖組件代碼實(shí)例解析
這篇文章主要介紹了Restful_framework視圖組件代碼實(shí)例解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-11-11
下面小編就為大家?guī)硪黄猵ython win32 簡單操作方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-05-05
Python3標(biāo)準(zhǔn)庫之threading進(jìn)程中管理并發(fā)操作方法
這篇文章主要介紹了Python3標(biāo)準(zhǔn)庫之threading進(jìn)程中管理并發(fā)操作方法，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-03-03
python實(shí)現(xiàn)Dijkstra算法的最短路徑問題
這篇文章主要介紹了python實(shí)現(xiàn)Dijkstra算法的最短路徑問題，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-06-06
一起來學(xué)習(xí)一下python的數(shù)字類型
這篇文章主要為大家詳細(xì)介紹了python的數(shù)字類型，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
這篇文章主要介紹了Python 類的私有屬性和私有方法,結(jié)合實(shí)例形式分析了Python面向?qū)ο蟪绦蛟O(shè)計(jì)中類的私有屬性與私有方法簡單操作技巧,需要的朋友可以參考下2019-09-09
python GUI庫圖形界面開發(fā)之PyQt5切換按鈕控件QPushButton詳細(xì)使用方法與實(shí)例
這篇文章主要介紹了python GUI庫圖形界面開發(fā)之PyQt5切換按鈕控件QPushButton詳細(xì)使用方法與實(shí)例,需要的朋友可以參考下2020-02-02