阮一峰的这篇文章，字符串匹配的KMP算法，能够很好地帮助我们理解KMP的大致思路。如果需要从原理上更深入和全面的理解，比如在text processing问题中常用的自动机表示，可以参考UCI的一个Lecture Note。
网上有各种实现，这里选取比较容易理解并且合乎逻辑的一则来讨论。
# 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]这样两处。
首先第一个，j = lps[j-1]。当j==M，即找到匹配时，将pattern的cursor也就是j移动到lps[j-1]处。为什么不是lps[j]处呢，其实很容易理解，因为pattern和lps数组都是zero based，lps是longest proper prefix which is also suffix，那么从零开始，应当是要有-1存在的。同理，不匹配的情况中，j != 0时，j = lps[j-1]。
第二个，computeLPSArray方法中的len = lps[len-1]。既然都不匹配了，那么该处的lps不是应该变成0吗？要注意的是，在这个方法中，pattern字符串(数组)的cursor是i，而不是len，并且，len = lps[len-1]之后，i并没有变化。在某些情况，比如AAACAA，当i==3的时候，的确该处的lps是0，但是len并不表示某处的lps，而是一个中间量，用于表示lps。这里，如果pat[i]==pat[len]或者len一直不满足，那么len = lps[len-1]将一直执行。因为lps[0]始终是0，所以循环肯定是会终止的。len = lps[len-1]在这里到底是什么含义呢？其实可以把len理解成一个对于前缀的cursor，让这个cursor往前（往index 0）移动，这样在下一次pat[i]==pat[len]的比较，前缀cursor回退了。
举例来说，在AAACAAAAA这个pattern中，当刚刚运行到i==7时，len==lps[6]==3，这个时候比较pat[3]字符C和pat[7]字符A，不相等。所以我们自然而然地想要减小前缀再比较。而这个过程，就是回退前缀的cursor，表达出来，也就是len=lps[len-1]。
