# Knuth–Morris–Pratt
###### tags: `Algorithm` `Knuth–Morris–Pratt`
**step 1 get Partial Match Table 找出最長公共前綴表**

Q1:為什麼需要這個表?
這個表的用意在當匹配失敗時可找到上一個相同字串,而不是重頭開始重新比對
ex: abcde
前綴 :
abcd
abc
ab
a
後綴 :
bcde
cde
de
e

abcdabc
a -> 0
ab -> 0
abc -> 0
abcd -> 0
abcda -> 1
abcdab -> 2
abcdabc ->3

PMT
a b c d a b c
0 0 0 0 0 1 2
為了程式設計的方便， 不直接使用PMT陣列，而是將PMT陣列向後偏移一位
第0位的值，將其設成了-1，這只是為了程式設計的方便，並沒有其他的意義。
a b c d a b c
-1 0 0 0 0 0 1 2

**step 2 mapping**
target string : abceabcdabc
mapping string : abcabc

a b c e a b c d a b c
a b c d a b c

比對到'e'與'd'時發現不相同
則將mapping table移動到'd'的前綴表值
d的前綴表值為0

a b c e a b c d a b c
a b c d a b c

再次筆對'e'與目前mapping table且不相同
則找到'a'的前綴表值為-1即表示往後推進一位

a b c e a b c d a b c
a b c d a b c

**程式面**
取得前綴表
a 0
ab 0
abc 0
abcd 0
abcda 1 <-
abcdab 2
abcdabc 3
key1 : 取下一層新增的元素 與 上一層的共用元素的下一個相比
ex
s1 = abcda p_len = 1
s2 = abcdab
當s2要滿足PMT時 s2[prefix] 勢必要等 新增的元素 s2[last] = 'b'

key2: 當下一層沒有匹配時需往上一層上上一層...回推到 index = 0
回推的方法為 找到上上層prefix table所指向的char
s1 = abcdab p_len = 2
s2 = abcdaba
step 1
s2[p_len] <> s2[last]
step 2
p_len = prefix_table [p_len-1]
s2[p_len] <> s2[last]
.... 直到找到index為0