阮一峰的這篇文章啥酱，字符串匹配的KMP算法挡爵，能夠很好地幫助我們理解KMP的大致思路姆泻。如果需要從原理上更深入和全面的理解火窒，比如在text processing問題中常用的自動(dòng)機(jī)表示硼补，可以參考UCI的一個(gè)Lecture Note。
網(wǎng)上有各種實(shí)現(xiàn)熏矿，這里選取比較容易理解并且合乎邏輯的一則來(lái)討論已骇。
源自geeksforgeeks离钝。
# Python program for KMP Algorithm
def KMPSearch(pat, txt):
M = len(pat)
N = len(txt)
# create lps[] that will hold the longest prefix suffix
# values for pattern
lps = [0]*M
j = 0 # index for pat[]
# Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps)
i = 0 # index for txt[]
while i < N:
if pat[j] == txt[i]:
i+=1
j+=1
if j==M:
print "Found pattern at index " + str(i-j)
j = lps[j-1]
# mismatch after j matches
elif i < N and pat[j] != txt[i]:
# Do not match lps[0..lps[j-1]] characters,
# they will match anyway
if j != 0:
j = lps[j-1]
else:
i+=1
def computeLPSArray(pat, M, lps):
len = 0 # length of the previous longest prefix suffix
lps[0] # lps[0] is always 0
i = 1
# the loop calculates lps[i] for i = 1 to M-1
while i < M:
if pat[i]==pat[len]:
len+=1
lps[i] = len
i+=1
else:
if len!=0:
# This is tricky. Consider the example AAACAAAA
# and i = 7
len = lps[len-1]
# Also, note that we do not increment i here
else:
lps[i] = 0
i+=1
txt = "ABABDABACDABABCABAB"
pat = "ABABCABAB"
KMPSearch(pat, txt)
比較需要理解的，是j = lps[j-1]和len = lps[len-1]這樣兩處褪储。
首先第一個(gè)卵渴，j = lps[j-1]。當(dāng)j==M鲤竹，即找到匹配時(shí)浪读，將pattern的cursor也就是j移動(dòng)到lps[j-1]處。為什么不是lps[j]處呢辛藻，其實(shí)很容易理解碘橘，因?yàn)閜attern和lps數(shù)組都是zero based，lps是longest proper prefix which is also suffix吱肌，那么從零開始痘拆，應(yīng)當(dāng)是要有-1存在的。同理氮墨，不匹配的情況中纺蛆，j != 0時(shí)，j = lps[j-1]规揪。
第二個(gè)桥氏，computeLPSArray方法中的len = lps[len-1]。既然都不匹配了猛铅，那么該處的lps不是應(yīng)該變成0嗎识颊？要注意的是，在這個(gè)方法中奕坟，pattern字符串(數(shù)組)的cursor是i祥款，而不是len，并且月杉，len = lps[len-1]之后刃跛，i并沒有變化。在某些情況苛萎，比如AAACAA桨昙，當(dāng)i==3的時(shí)候，的確該處的lps是0腌歉，但是len并不表示某處的lps蛙酪，而是一個(gè)中間量，用于表示lps翘盖。這里桂塞，如果pat[i]==pat[len]或者len一直不滿足，那么len = lps[len-1]將一直執(zhí)行馍驯。因?yàn)?code>lps[0]始終是0阁危，所以循環(huán)肯定是會(huì)終止的玛痊。len = lps[len-1]在這里到底是什么含義呢？其實(shí)可以把len理解成一個(gè)對(duì)于前綴的cursor狂打，讓這個(gè)cursor往前（往index 0）移動(dòng)擂煞，這樣在下一次pat[i]==pat[len]的比較，前綴cursor回退了趴乡。
舉例來(lái)說对省，在AAACAAAAA這個(gè)pattern中，當(dāng)剛剛運(yùn)行到i==7時(shí)晾捏，len==lps[6]==3官辽，這個(gè)時(shí)候比較pat[3]字符C和pat[7]字符A，不相等粟瞬。所以我們自然而然地想要減小前綴再比較同仆。而這個(gè)過程，就是回退前綴的cursor裙品，表達(dá)出來(lái)俗批，也就是len=lps[len-1]。
