KMP算法值得一看的一個例子

KMP (Knuth-Morris-Pratt)算法是一種用于在一個文本串S內查找一個模式串P的字符串匹配算法。它是由Donald Knuth，Vaughn Pratt和James H. Morris在1977年設計的。 KMP算法的主要優(yōu)點是利用了匹配失敗的信息來減少模式串與文本串的匹配次數，從而提高了字符串匹配的效率。時間復雜度是 O(n+m)

下面是一個簡單的 KMP 算法示例，它在文本串S中查找模式串P的第一個匹配位置：

　　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] = 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:

? ? ? 　　? ? ? # This is tricky. Consider the example.

? ? ? 　　? ? ? # AAACAAAA and i = 7. The idea is similar

? ? ? ? 　　? ? # to search step.

? ? ? ? ?　　? ?if len != 0:

? ? ? ? 　　? ? ? ? len = lps[len-1]

? ? ? ? 　　? ? else:

? ? ? ? ? ? 　　? ? lps[i] = 0

? ? ? ? ? 　　? ? ? i += 1

　　txt = “ABABDABACDABABCABAB”

　　pat = “ABABCABAB”

　　KMPSearch(pat, txt)