motif的中文直接翻譯是「主題」
在生物資訊中，motif中文可稱作模體，意思是在DNA或RNA或蛋白質上，重複出現的片段、小區段，通常是被蛋白質「辨識、結合」的區域。
這些片段不需要完全一模一樣，可以容忍有一些不同
motif這名詞取的真不錯
要比喻的話，我會稱他是「旋律」
像是慶祝生日的這首「生日快樂歌」
每個人的發音不同、樂器的音色不同，甚至有節奏差異
但旋律一聽我們耳熟能詳，能辨識出對方在彈唱的音樂
甚至把「祝你生日快樂」唱成 「豬你生ｚ怪了」有一些詞彙上的差異
只要旋律對了，我們還是能聽的懂，不影響認知
或者在金融市場上，看到特定pattern的K線圖、均線排列
代表這支股票正在多頭走勢，就像聽到股票即將起飛的旋律
不過胡扯一通
其實這一題與上面的概念都無關，單純只要尋找「子字串匹配」就可以了
不用什麼模糊匹配、模糊搜尋、模糊辨識
子字串匹配只是其中一種尋找Motif的方法
是最簡單、最基本的搜尋方式，但是通常「不夠準確」
輸入：
GATATATGCATATACTT
ATAT
輸出：
2 4 10
給一段序列GATATATGCATATACTT
尋找並記錄ATAT重複片段的起始點位置
程式碼：
暴力破解，雙層for迴圈 處理字元比對
s = "GATATATGCATATACTT"
sub = "ATAT"
positions = []
for i in range(0, len(s) - len(sub) + 1):
match = True
for j in range(len(sub)):
if s[i + j] != sub[j]:
match = False
break
if match:
positions.append(i + 1)
for m in positions:
print(m, end=" ")
暴力破解，寫成函式
利用python字串比對的寫法
if s1 == s2:
或者
if s[i:i+len(t)] == t:
但其實底層也是跑一層for迴圈（處理字元比對），效率相同
def find_substring_locations(s, t):
positions = []
for i in range(len(s) - len(t) + 1):
if s[i:i + len(t)] == t:
positions.append(i + 1) # 位置從1開始計算位置
return positions
# 等價的寫法，列表推導式
# def find_substring_locations(s, t):
# return [
# i + 1 # 位置從1開始計算位置
# for i in range(len(s) - len(t) + 1)
# if s[i:len(t) + i] == t
# ]
s = "GATATATGCATATACTT"
sub = "ATAT"
print(" ".join(map(str, find_substring_locations(s, sub))))
KMP演算法
(文長、燒腦、吐血）
KMP演算法是1977年由三位大學教授提出的：Knuth、Morris、Pratt 字串匹配的經典算法
暴力解法是每次都重新從頭比對
但其實在比對失敗後，可以很明顯的拿「下一個位置」直接套上去繼續比
靠「已經比對成功的部分」來建一張表（失敗表），在比對失敗時回退「之前成功的長度」來避免重複工作量
失敗表(Failure Table)名詞也很多種：
又稱
LPS表(最長前綴後綴表, Longest Prefix Suffix Table)
Next表(Next Array)
部分匹配表(Partial Match Table)
回跳表(Jump Table / Skip Table)
打破對KMP的錯誤幻想
第一次練習的同學，才需要看這一段，提幾個容易誤解的地方
這不是ＫＭＰ這不是肯德基
主字串：ABAAAABABA
子字串：BAB
主串BAA與BAB對不上
我在比對到失敗以後，直接找下一個B來比對就好，略過中間所有的AAA...
這豈不就是「跳過」的解法嗎？
=> 這只是帶有「人為優化」的直覺，誤以為是跳著比對
實際上在做的事情還是「暴力破解」，一個個比對
挪動主串、挪動子串？
看這兩張round1 round2的比對
挪動子串的做法
挪動主串的做法
大家都說KMP是「移動子串」，但其實也可以說KMP是「移動主串」
兩者只是視角不同，一個相對的概念而已，本質上是做一樣的事情。
因為在這道題中，只有A、B兩字串比對
若整個宇宙只有A、B兩物體，那麼以下兩者完全等價
A固定、B移動 <=> A移動、B固定
失敗表怎麼推算？
『字串前綴與後綴有多少相似（重疊），記錄重疊的長度n』
這樣子一旦比對失敗後，就能知道 下一個主字串要與「子字串的第n個位置」開始比對
首先請試著照你腦中所想，填寫以下欄位
１號練習題 字串："AABBABABBA"
網路上很多教學的範例，會讓人覺得是尋找出“最大重複字串長度”
然而實際上概念卻是“前綴（最開頭）vs後綴（最尾端）”
只准許找頭尾，有這樣一個限制
答案如下
如果你的答案第一次就正確，那麼恭喜有理解前綴、後綴的意思
（失敗表的開頭從 -1或0 開始建表都可以，先加一或減一的區別而已，
網路上兩種做法都有，只要在最終整個KMP的比對邏輯配合一致就行
此篇文章以0為主）
若仍不理解，多看幾遍這段敘述
失敗表：『包含「最近加入進來的字」的字串，與字串的開頭有多麽相像』的分數
再看另一題 ２號練習題
字串："AABAABBAAA"
最後再來看一題 ３號練習題
字串："AAABAAAAAB" 這題是最複雜也是有陷阱的
３號練習題 後半段過程：
若都能答對
代表手推算完全會了，再來就是如何用邏輯流程建立失敗表
（用人眼看很快、要寫程式反而難，很神奇吧大腦）
建議：至少手邊有紙張，真正推算過一次，因為等一下會用到
嘗試建立失敗表
參考 １號練習題
首先要建立好第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))
BM演算法
還有個東西叫作 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的，我從不從頭開始，我會記住哪裡開始錯。」