---
# System prepended metadata

title: Knuth–Morris–Pratt
tags: [Algorithm, Knuth–Morris–Pratt]

---

# 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