假設(shè)有兩個字符串：t(目標串啰扛，長度n)和p(模式串嚎京，長度m)嗡贺，通常m<<n。
樸素串匹配算法
- 優(yōu)點
簡單易懂 - 缺點
效率低
時間復(fù)雜度分析：最壞的情況是每一趟都在模式串的最后遇到不匹配鞍帝，那么每一趟比較的次數(shù)是n-m+1, 總的比較次數(shù)是 mx(n-m+1), 因為m<<n, 所以時間復(fù)雜度為O(mxn)
代碼實現(xiàn)：
def naive_match(t,p):
m, n = len(p), len(t)
i, j = 0, 0
while i < m and j < n:
if p[i] == t[j]:
i, j = i+1, j+1
else: #字符不匹配诫睬，考慮t串的下一個位置
i, j = 0, j-i+1 # j-i+1為相對位置加1
if i == m: # p串完全匹配后（i++）i的值變?yōu)閙
return j-i #此時j的值減去p串的長度（i或者m）就是所在下標
return 'No Match!' #無匹配則返回'No Match'
#實例化
t = ' abc de'
p = 'de'
print naive_match(t, p)
#輸出 6
#換一種想法去實現(xiàn)
def naive_match1(p,t):
m, n, i = len(p), len(t), 0
for i in range(n-m+1):
if t[i:i+n-1] == p:
return i
return 'No match!'
p = 'abc'
t = 'abdabc'
print naive_match1(p,t)
KMP算法（無回溯串匹配算法）
分析：算法的關(guān)鍵在于構(gòu)建一個跳轉(zhuǎn)表(pnext表)，當?shù)趇個字符匹配失敗時不是重新從頭開始匹配（例如樸素串匹配算法）帕涌，而是通過構(gòu)建好的跳轉(zhuǎn)表跳轉(zhuǎn)到第j個字符摄凡。例如：
0 1 2 3 4 5 6 7 # 字符串的位置
a b c a b c d a # p串
0 0 0 0 1 2 3 0 # pnext表，如果匹配不成功 跳轉(zhuǎn)的位置
解釋：當?shù)?位的字符d匹配失敗后可以直接跳轉(zhuǎn)到第3位的a蚓曼， 因為它們之前的abc是相同的亲澡，不需要再匹配一遍了。
更近一步分析：如果p串i位置與t串的j位置匹配失敗了纫版，先去查找p串i位置之前的從0開始的串（假設(shè)[0,k], k<i）與t串j位置之前的串（[j-k,j]）是否有相同的片段床绪，如果有找出那個k值，若木有則按照樸素匹配算法進行其弊。
移動的位數(shù) = 已匹配的字符數(shù) - 對應(yīng)的部分匹配值（查表）
如何得到p串每個字符的部分匹配值（如何生成next表）癞己？
對于每個p串的字符，前綴與后綴共有字符的個數(shù)就是該字符的部分匹配值梭伐。 詳細解釋
那么如何構(gòu)造部分匹配表（next表）呢痹雅，python代碼如下：
Next表 （部分匹配表，跳轉(zhuǎn)表）
def partial_table(p):
prefix = set() #集合
postfix = set()
ret = [0] #存放p串匹配值糊识，因為第一個字符的匹配值肯定為0绩社，先把0存進去
for i in range(1,len(p)): #從第二個字符開始
#獲取前i+1個字符串的前綴（例如對于abc，前綴有a,ab）
#Note:切片[0:3]-->索引0,1,2（第一個索引是0可以省略-->[:3]-->取前三個數(shù)）
#Note:range函數(shù)也一樣取不到后面的數(shù)-->rang(1,3)-->>1,2
prefix.add(p[:i]) #因為對于不同的字符前綴都有相同的部分赂苗，這里只需要添加就行了
#獲取前i+1個字符串的后綴(例如對于abc愉耙，后綴有bc,c)
postfix = {p[j:i+1] for j in range(1,i+1)} #對于不同的字符后綴總是不一樣
ret.append(len(prefix&postfix))
return ret
KMP算法實現(xiàn)
#-*-coding=utf-8-*-
#KMP
def kmp_match(t, p):
m,n = len(t),len(p)
cur = 0 #起始指針cur
table = partial_table(p)
while cur <= m-n: #最多做m-n趟匹配
for i in range(n): #在每一趟比較中
if s[i+cur]!=p[i]: #匹配不成功時
cur += max(i - table[i-1], 1) #移動的位數(shù) = 以匹配的字符數(shù) - 匹配值
break
else:
return True
return False
# 測試
p = 'ABCDABD'
s = 'BBC ABCDAB ABCDABCDABDE'
print partial_table(p)
print kmp_match(s, p)
