KMP是用來做「字串搜索比對」用的
(文長、燒腦、吐血）
KMP演算法是1977年由三位大學教授提出的：Knuth、Morris、Pratt 字串匹配的經典算法
暴力解法是每次都重新從頭比對
但其實在比對失敗後，可以很明顯的拿「下一個位置」直接套上去繼續比
靠「已經比對成功的部分」來建一張表（失敗表），在比對失敗時回退「之前成功的長度」來避免重複工作量
失敗表(Failure Table) 名詞也很多種，又稱：
第一次練習的同學，才需要看這一段，提幾個容易誤解的地方
以下這種方法不算是KMP
主字串：ABAAAABABA
子字串：BAB
上排是主串、下排是子串，下排是會往右滑動的
一開始比對失敗（紅框處），往右移（橘框處），但此時主串BAA仍與BAB對不上
當我在比對到失敗以後，直接找下一個B來比對就好（黃框處），略過中間所有的AAA...
這豈不就是「跳過」的解法嗎？
=> 其實這只是帶有「人為優化」的直覺，誤以為是跳著比對
實際上在做的事情還是「暴力破解」，一個個比對
為什麼？因為要怎麼讓電腦知道跳到下一個B？豈不得一個個往右找、比對才知道，仍然是暴力
看這兩張round1 round2的比對
大家都說KMP是「移動子串」，但其實也可以說KMP是「移動主串」
兩者只是視角不同，一個相對的概念而已，本質上是做一樣的事情。
因為在這道題中，只有A、B兩字串比對
若整個宇宙只有A、B兩物體，那麼以下兩者完全等價
A固定、B移動 <=> A移動、B固定
會有一排字串、以及一排分數
你會看到如果字母相同，分數會累加
這排分數代表意義就是
「字串前綴與後綴有多少相似（重疊），記錄重疊的長度n」
這樣子一旦比對失敗後，就能知道 下一個主字串要與「子字串的第n個位置」開始比對
看不懂？沒關係，請先繼續往下
首先請試著照你腦中所想，填寫以下欄位
網路上很多教學的範例，讓人覺得失敗表是尋找出「最大重複字串長度」
然而實際上，失敗表的概念卻是找「前綴（最開頭）vs 後綴（最尾端）」
只準許找頭尾，有這樣一個限制
答案如下
如果你的答案第一次就正確，那麼恭喜有理解前綴、後綴的意思
（如果用的是「最大重複字串長度」，那麼你推出來會是錯誤的那行）
若仍不理解，多看幾遍這段敘述
失敗表：『包含「最近加入進來的字」的字串，與字串的開頭有多麽相像』的分數
如果是錯誤的那行，最終會得到長度為4的"ABBA"子字串，然而這是「最大重複字串長度」，而不是「前綴（最開頭）vs 後綴（最尾端）」。
如果要長度為4，那麼子字串必須是"AABB"，但很可惜此題沒有
順帶一提，失敗表的開頭從 -1或0 開始建表都可以，只是先加一或減一的區別而已，網路上兩種做法都有，只要在最終整個KMP的比對邏輯配合一致就行。
此篇文章以0為主
再看另一題
最長的時候"AAB"長度3
最終跑完終點"AA"長度2
最後再來看一題
這題是最複雜也是有陷阱的
３號練習題 後半段過程：
若都能答對
代表手推算完全會了，再來就是如何用邏輯流程建立失敗表
（用人眼看很快、要寫程式反而難，很神奇吧大腦）
建議：至少手邊有紙張，真正推算過一次，因為等一下會用到
參考 １號練習題
首先要建立好第1項（索引為0），在迴圈里面才能開始跟後面第2、第3項比對
# 一開始寫 step1
def build_table_step1(t):
table = [0] # 先建好第0項 失敗表[0]
length = 0 # 目前位置的 最長(前綴=後綴)的長度，是失敗表所填入的數字
for i in range(1, len(t)): # 從第2項（索引為1)開始比對
if t[i] == t[length]: # 若兩者合得來，combo數+1
length += 1
table.append(length)
else:
length = 0 # => 寫法錯誤，但先這樣試試
table.append(length)
return table
# １號練習題
print(build_table_step1("AABBABABBA")) # [0, 1, 0, 0, 1, 0, 1, 0, 0, 1]
# ２號練習題：
print(build_table_step1("AABAABBAAA")) # [0, 1, 0, 1, 2, 3, 0, 1, 2, 0(*)]
哇，直接通過１號練習題測資
天哪，好簡單喔！
但是馬上死在２號練習題
最後一項，很明顯是死在else處的邏輯
因為比對錯誤後不可以直接寫0，必須「延續」上一個同樣為A的數值
# 接著到 step2
def build_table_step2(t):
table = [0]
length = 0
for i in range(1, len(t)):
if t[i] == t[length]:
length += 1
table.append(length)
else:
# length = table[i - 1] # => 寫法錯誤：改成延續「前一項數值」，其實不對
length = table[length - 1] # => 改成這樣會更接近一點，回退、跳到上一個紀錄資訊（存檔點）=> 但也還不對
table.append(length)
return table
# １號練習題
print(build_table_step2("AABBABABBA")) # [0, 1, 0, 0, 1, 0, 1, 0, 0, 1]
# ２號練習題：
print(build_table_step2("AABAABBAAA")) # [0, 1, 0, 1, 2, 3, 0, 1, 2, 1(*)]
但不是傻傻「延續」上一個數值，而是要「回跳」上一個紀錄點（table）
可是，當回跳以後，仍然死在２號練習題
「回跳」的意思是這樣子的：
所有的「Jump點」，遭遇比對失敗以後，都要直接跳回＊處，從此重生點繼續往右比對
那麼，跳回＊之後呢，要做什麼處理？
失敗直接給0嗎？跳回只能有一次？
好啊，越來越接近答案了
於是先來看看３號練習題測試資料，從中間開始往下
也就是說
一旦「下一個字比對失敗」，就必須依腳下所踩著的數字，回跳到該數字的位置（索引）
如果「下一個字」與「回跳回去的字（索引的字）」比對成功，那就掛著該數字啦～
如果比對失敗，那就「二段跳」、再失敗「三段跳」...一直按腳底下的數字跳回更前面
打個比喻：戀愛KMP學
下一個字元，如果匹配成功（相親成功），combo+=1
如果匹配失敗（跟下一位對象不合）我就回去找前一任女朋友
如果與前一任女友匹配成功，我就與她繼續走下去
前一任女友不理我（匹配失敗），我就再回去找更前一任女朋友
# 接著到 step3
def build_table_step3(t):
table = [0]
length = 0
for i in range(1, len(t)):
# 失戀就找上一任女友，直到合得來 or 恢復單身
while length > 0 and t[i] != t[length]:
length = table[length - 1]
# 哇，下一個對象是我合的來的人，直接變女友
if t[i] == t[length]:
length += 1
# 原本else處程式碼，已改寫成上面的while邏輯了
table.append(length)
return table
# １號練習題
print(build_table_step3("AABBABABBA")) # [0, 1, 0, 0, 1, 0, 1, 0, 0, 1]
# ２號練習題：
print(build_table_step3("AABAABBAAA")) # [0, 1, 0, 1, 2, 3, 0, 1, 2, 2]
# ３號練習題：
print(build_table_step3("AAABAAAAAB")) # [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]
好的好的，這樣改寫完以後，三個練習測資都能過了
代表KMP最難的部分——「失敗表」已經完成
有了失敗表後，在比對失敗時，能從第幾個開始繼續比對（跳過幾次步驟）
接著來實作主程式
這里要捨棄「雙層for迴圈」比對的方式（不然又會變成暴力解）
要擁抱「匹配成功，combo+=1」的概念
# 主程式 step1
def kmp_search_step1(s, t):
positions = []
table = build_table_step3(t) # 建立失敗表
length = 0
for i in range(len(s)): # 不是從1開始喔，而是也須要比對[0]
# for j in range(len(t)): # 不是這種雙迴圈的寫法喔！
# ...
if s[i] == t[length]: # 字元比對成功
length += 1
# else: # 1. 字元比對失敗，這里要做什麼？
# ???
if length == len(t): # 字串完全匹配
positions.append(i) # 2. 錯誤寫法，底下length也不該歸0
length = 0
return positions
s = "GATATATGCATATACTT"
sub = "ATAT"
print(kmp_search_step1(s, sub)) # [4, 10, 15] 錯誤 => 正確答案是 [2, 4, 10]
有兩個地方要修正
# 主程式 step2
def kmp_search_step2(s, t):
positions = []
table = build_table_step3(t)
length = 0
for i in range(len(s)):
while length > 0 and s[i] != t[length]:
length = table[length - 1]
if s[i] == t[length]: # 字元比對成功
length += 1
# 原本else處程式碼，已改寫成上面的while邏輯了
if length == len(t): # 字串完全匹配
positions.append(i - length +2) # 起點位置：i - length + 1，且index預設為0，需再+1
length = table[length - 1] # 匹配完重設回前一個 ex: 主字串：AAAA、子字串：AA
return positions
s = "GATATATGCATATACTT"
sub = "ATAT"
print(kmp_search_step2(s, sub)) # [2, 4, 10]
最終程式碼：
def kmp_search(s, t):
positions = []
table = build_table(t)
length = 0
for i in range(len(s)):
while length > 0 and s[i] != t[length]:
length = table[length - 1]
if s[i] == t[length]: # 字元比對成功
length += 1
if length == len(t): # 字串完全匹配
positions.append(i - length + 2) # 起點位置：i - length + 1，且index預設為0，需再+1
length = table[length - 1] # 匹配完重設回前一個 ex: 主字串：AAAA、子字串：AA
return positions
def build_table(t):
table = [0]
length = 0
for i in range(1, len(t)):
# 失戀就找上一任女友，直到合得來 or 恢復單身
while length > 0 and t[i] != t[length]:
length = table[length - 1]
# 哇，下一個對象是我合的來的人，直接變女友
if t[i] == t[length]:
length += 1
table.append(length)
return table
s = "GATATATGCATATACTT"
sub = "ATAT"
print(kmp_search(s, sub))
還有個東西叫作 Boyer-Moore，這是目前最實際應用中最快的比對演算法
字串搜尋工具grep就使用這一套
什麼，你想學？真的假的難道你已經被KMP燒壞腦袋了嗎
這邊只附程式碼，未來有機會再提BM演算法
程式碼：
def boyer_moore(text, pattern):
m, n = len(pattern), len(text)
if m == 0:
return []
# 建立壞字元表
bad_char = {}
for i in range(m):
bad_char[pattern[i]] = i
print(bad_char)
result = []
shift = 0
while shift <= n - m:
j = m - 1
while j >= 0 and pattern[j] == text[shift + j]:
j -= 1
if j < 0:
result.append(shift + 1) # 1-based index
# 原本是 shift += m，但這會跳過重疊
# 改為根據下一個壞字元跳，或至少右移一格
shift += 1
else:
last = bad_char.get(text[shift + j], -1)
shift += max(1, j - last)
return result
s = "GATATATGCATATACTT"
sub = "ATAT"
print(boyer_moore(s, sub))
（N代表主字串長度、M代表是子字串長度）
暴力破解法：平均O(N+M)、最差O(Ｎ×Ｍ)；
有加mismatch（不匹配就break）的話其實隨機資料的平均與KMP差不多
KMP演算法：平均O(N+M)、最差O(N+M)
平均與最差都相同，最穩定發揮
Boyer-Moore：平均Ｏ(N/M)、最差O(N×M)
平均超級快，但是遇到最差情形會爆炸、退化成暴力法相同（運氣好跳超快，省去一堆功夫；但遇到字母種類少又重複時，跳不動）
基因序列的高重複性（只有ATCG）四個字元，字母數太少
不適合使用Boyer-Moore，容易退化變得更慢
如果是 英文字母（A-Z）或者中文字比對
字元集大小較大，遇到一樣的字母機遇較低，才適合Boyer-Moore
KMP非常井然有序，整體來說穩定發揮
每一次都“狹帶著充足資訊”進行「隱性遞迴」
「我去面試的時候，主管問我有沒有resilience（韌性）」
我回答：「我是學KMP的，我從不從頭開始，我會記住哪里開始錯。」
iThome鐵人賽
看影片追技術