KMP演算法
KMP演算法
一個人能走的多遠，不在於他在順境時能走多快，而在於在逆境時多久能找到曾經的自己
最長共通前綴後綴
Longest Common Prefix Also Suffix，簡稱LPS。
“abab”的前綴有[“a”,”ab”,”aba”]，後綴有[“b”,”ab”,”bab”]，所以LPS是”ab”。
Partial Match Table
部分匹配表格，簡稱PMT。在KMP使用時又稱Failure Function，因為只有在匹配失敗時用到。
計算p的每個子字串的LPS長度。
| i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| p[i] | a | b | a | b | c |
| substring | a | ab | aba | abab | ababc |
| LPS | 0 | 0 | 1 | 2 | 0 |
例如i=4，ababc和ababb匹配失敗時，至少”abab”部分是匹配成功的，而”abab”有LPS=2，代表可以重複利用最後兩個字元”ab”。i回退到PMT[3]=2的位置，也就是p[2]的”a”繼續匹配，省略第一次出現的”ab”比對。
Next Table
只有當第i個字元匹配失敗時才會用到PMT[i-1]，所以PMT最後一格永遠不會用到。而且要特別處理i=0匹配失敗時的特例，因為PMT[-1]不存在。
為了方便計算，把PMT整個往右移一格，table[0]設為-1。之後在i失敗時直接回退到table[i]。只有在目標字串第一個字元就匹配失敗時，才會讓j變成-1，此時兩方的索引同時+1。
| i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| p[i] | a | b | a | b | c |
| table | -1 | 0 | 0 | 1 | 2 |
KMP字串比對
來源字串s，目標字串p，長度分別為M, N。
先以p建立next table。
i, j分別為s, p的指針，初始值0，每次比對s[i]和p[j]，是否相同：
- 若s[i]=s[j]，兩者同時+1
- 若j=-1，一樣兩者+1
- 否則將j退回至table[j]的位置
重複至其中一個字串全部讀取完為止。若j=N則表示成功找到目標字串p，其起始索引為i-j；否則匹配失敗，回傳-1。
最後整合練習
s=”abaababaca”
p=”abac”
先以p建立next table：
table[0]=-1
i=1, prefix=”a”, suffix=”b”, LPS=0, table[1]=0
i=2, prefix=”ab”, suffix=”ac”, LPS=0, table[2]=0
i=3, prefix=”aba”, suffix=”bac”, LPS=1, table[3]=1
table=[-1,0,0,1]
利用table進行比對：
i=j=0
s[0]=p[0], i++, j++ 已找到”a”
s[1]=p[1], i++, j++
已找到”ab”
s[2]=p[2], i++, j++
已找到”aba”
s[3]!=p[3], j=table[3]=1
已找到”a”
s[3]!=p[1], j=table[1]=0
已找到””
s[3]=p[0], i++, j++
已找到”a”
s[4]=p[1], i++, j++
已找到”ab”
s[5]=p[2], i++, j++
已找到”abc”
s[6]!=p[3], j=table[3]=1
已找到”a”
s[6]=p[1], i++, j++
已找到”ab”
s[7]=p[2], i++, j++
已找到”aba”
s[8]=p[3], i++, j++
已找到”abac” 比對結束
p的起始位置為j-i=5
心得
字串比對時，基本上j的位置等價於已經成功找到的字元數，因此j和目標字串長度相等也代表成功找到。
next table、partial match table、prefix function和failure function在KMP文章出現時，指的都是同個東西，只是有些版本會將其右移一格方便計算。
建表的時候i=1, j=0
KMP的時候i=0, j=0
KMP只有三種情況：
- 成功，兩個都右移
- 失敗，j還有辦法左移就左移
- 失敗，j已經在起點了，只好把i右移
2023-9-14更新：
好像其實原版的PMT比較好用，用得人也多，盡量用原版的就好。
程式碼
參考資料
https://yeefun.github.io/kmp-algorithm-for-beginners/
https://www.zhihu.com/question/21923021/answer/281346746
https://zhuanlan.zhihu.com/p/36190375
https://cmps-people.ok.ubc.ca/ylucet/DS/KnuthMorrisPratt.html
https://oi-wiki.org/string/kmp/
https://www.zhihu.com/question/21923021/answer/37475572