# -*- coding: utf-8 -*-
"""
Created on 2020-04-02 16:01:54
簡介：KMP字符串匹配
@author: 楊h yh4241@foxmail.com
"""
def gen_pnext(substr):
m = len(substr)
pnext = [0]*m
j = 0
i = 1
while i < m:
if substr[j] == substr[i]:
pnext[i] = j+1
j += 1
i += 1
elif j != 0:
j = pnext[j-1]
else:
pnext[i] = 0
i += 1
return pnext
gen_pnext('abcabgac')
# [out]:[0, 0, 0, 1, 2, 0, 1, 0]
def KMP_algh(string, substring):
pnext = gen_pnext(substring)
i, j = 0, 0
n = len(string)
m = len(substring)
while j<m and i<n:
if substring[j] == string[i]:
j += 1
i += 1
elif j!=0:
j = pnext[j-1]
else:
i += 1
if j == m:
return i-j
else:
return -1
KMP_algh('abgabcabgacyf','abcabgac')
#[out]:3
KMP字符串匹配算法
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門捂蕴，熙熙樓的掌柜王于貴愁眉苦臉地迎上來譬涡，“玉大人，你說我怎么就攤上這事啥辨∥性龋” “怎么了？”我有些...
- 文/不壞的土叔 我叫張陵溉知，是天一觀的道長陨瘩。 經(jīng)常有香客問我，道長级乍，這世上最難降的妖魔是什么舌劳？ 我笑而不...
- 正文 為了忘掉前任，我火速辦了婚禮玫荣，結(jié)果婚禮上蒿囤，老公的妹妹穿的比我還像新娘。我一直安慰自己崇决，他們只是感情好材诽，可當(dāng)我...
- 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著恒傻，像睡著了一般脸侥。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上盈厘，一...
- 文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼捐晶！你這毒婦竟也來了菲语？” 一聲冷哼從身側(cè)響起，我...
- 正文 年R本政府宣布婶恼，位于F島的核電站，受9級特大地震影響柏副，放射性物質(zhì)發(fā)生泄漏勾邦。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一割择、第九天 我趴在偏房一處隱蔽的房頂上張望眷篇。 院中可真熱鬧，春花似錦荔泳、人聲如沸蕉饼。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽昧港。三九已至，卻和暖如春支子，著一層夾襖步出監(jiān)牢的瞬間创肥，已是汗流浹背。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 今天看了kmp算法稽坤，最開始看得特別混亂，最后終于看明白了糯俗，想記錄一下尿褪。https://github.com/hym...
- getnext函數(shù)： 用來給出指示：如果當(dāng)前位置不匹配，要移動字串的位置多少得湘。這里引入了最大前綴和后綴的概念杖玲。 K...
