因為好像很多人還是不太懂，所以就嘗試PO篇文解釋一下KMP~~

如果有哪裡寫錯煩請告知>w<

---

為了方便說明我先定義一些符號:
字串(string)
一個字串S = a_1 a_2 a_3 … a_n 是一個字母組成的sequence(序列)
其中定義S[1] = a_1,
S[2] = a_2,
...
S[i] = a_i.

子字串(substring)
S[i:j]就表示 a_i a_i+1 … a_j-1 a_j //假設i<=j
我們稱S[i:j]為S的子字串，當然特別有S = S[1:n]。

EX: aaaab 就是 aaaaaabbb 的一個子字串

前綴(prefix)
一個字串是長這樣子的話S = |--------------|
那 S'= |------| S'就是S的一個prefix

嚴格來說如果一個字串是S = S[1:n]
那 S'= S[1:i] 當i<=n時，S;就是S的一個prefix

EX: a,ab,abc,abcd,abcde,abcdef 都是 abcdef 的前綴。

F函數
從字串S中的i位置往前延伸，最多可以往前幾位(< i)
使得往前的這個位數是S的前綴。

嗯看起來非常繞口的一句話= =...
從數學上來看就是最大的滿足S[i‐F(i)+1:i] = S[1:F(i)]的數 且 F(i)<i
不過如果不存在F(i) 就假設他 = 0吧～

想必還是不懂所以就舉個例子吧：

1 2 3 4 5 6 7 8 9 (index)
S = a b a b a a b a b
0 0 1 2 3 1 2 3 4 (F函數)

如果還是不懂 就我們一個一個來看@_@

F(1) = 0 因為 a babaabab
ababaabab

F(2) = 0 因為 ab abaabab
ababaabab

F(3) = 1 因為 aba baabab
a babaabab

F(4) = 2 因為 abab aabab
ab abaabab

F(5) = 3 因為 ababa abab
aba baabab
注意!雖然有 a babaabab 這樣子也可以match 但是不是最長前綴

F(6) = 1 因為 ababaa bab
a babaabab

F(7) = 2 因為 ababaab ab
ab abaabab

F(8) = 3 因為 ababaaba b
aba baabab
a babaabab 也是但是不是最長

F(9) = 4 因為 ababaabab
abab aabab
ab abaabab 也是但是不是最長

看了一堆例子之後想必對F函數有點感覺了吧= =+
而這個F函數其實就是ＫＭＰ的精隨!!

假設上面例子：如果 上面叫實體字串 下面叫虛擬字串
那當我們在配對實體字串的時候 同時也在配對虛擬字串!!

意思就是我們在配對S[1:i]的時候 同時也配對了S[1:F(i)]
遞迴的來說 我們也同時配對了S[1:F(F(i))]也配對了S[1:F(F(...F(i)...))]
（假設後面那項都>0的話）

就像F(9)在配對S[1:9]時 同時也配對S[1:F(9)] = S[1:4]
同時也配對S[1:F(F(9))] = S[1:F(4)] = S[1:2] ！！

有沒有清楚明白XD!? 好我假設有:p

那你可能會想 這個F函數有什麼鳥用呢= =?

就像老師上課說的因為當你把S跟T配對(T是pattern)時，
如果在某個時刻已經配對到"S中的i"跟"T中的j"也就是S[i-j+1:i] = T[1:j]
下一個要比對的就是S[i+1]跟T[j+1]是否相等？

如果相等的話很好i++, j++。
如果不相等呢？
因為我們已經有T[1:j]的資訊了，所以不用再重新跑一次！

因為我們知道S[i-j+1:i] = T[1:j]
S[i-F(j)+1:i] = T[1:F(j)]
S[i-F(F(j))+1:i] = T[1:F(F(j))]
S[i-F(F(..j..))+1:i] = T[1:F(F(..j..))]

所以我們可以直接把j變成F(j)

也就是比較S[i+1] T[F(j)+1]是不是相等？

如果相等的話很好i++, j=F(j)+1。（如果先做了j=F(j)那就只要j++就好了）
如果不相等呢？
這樣的情況跟上面最一開始的情況一樣了!!

總之就是一直做下去直到存在某個S[i+1] = T[F(F(..F(j)..))+1]

覺得符號很多頭昏眼花? 沒關係，讓我們來舉個例子。

0 1 2
1234567890123456789012
假設S = shikisfatabababahahaha
T = abababab
00123456 (T的F函式的值)

假設現在match情況是這樣 shikisfatababab ahahaha S[10:15] =
ababab ab T[1:6]
其中i=15, j=6。

則繼續往下比對之後會變成shikisfatabababa hahaha S[10:16] =
abababa b T[1:7]
其中i=16, j=7。
（因為S[16]==T[7]所以只要i++,j++就好了）


然後繼續往下比對 shikisfatabababa hahaha S[10:16]
abababa b T[1:7]
但是因為S[17]!=T[8] 即'h'!='b'所以會變成
shikisfatabababa hahaha S[12:16]
ababa bab T[1:F(7)] = T[1:5]
但是因為S[17]!=T[6] 所以變成
shikisfatabababa hahaha S[14:16]
aba babab T[1:F(5)] = T[1:3]
但是因為S[17]!=T[4] 所以變成
shikisfatabababa hahaha S[16:16]
a bababab T[1:F(3)] = T[1:1]
但是因為S[17]!=T[2] 所以變成
shikisfatabababa hahaha S[17:16]
abababab T[1:F(1)] = T[1:0]

有沒有點fu要怎麼用F來做比對了呢XDD?

那現在問題轉一下變成了 要如何求出F呢@@!?

我們可以利用一種類似遞推的方式

明顯的F(1) = 0
假設我們已經知道F(2) F(3) ... F(i-1) 那要怎麼求出F(i)呢?

其實仔細想一下的話 就會發現求出F的過程就ST匹配方式一樣哇!!

只是會變成T跟T自己做匹配而已:p

假設T = ababaabab

那麼一開始的話是
T = a babaabab i = 1
ababaabab j = 0
因為T[i+1]!=T[j+1] 且 j=0 所以F(2) = 0

T = ab abaabab i = 2
ababaabab j = 0
因為T[i+1]==T[j+1] 所以F(3) = j+1 = 1

T = aba baabab i = 3
a babaabab j = 1
因為T[i+1]==T[j+1] 所以F(4) = j+1 = 2

T = abab aabab i = 4
ab abaabab j = 2
因為T[i+1]==T[j+1] 所以F(5) = j+1 = 3

T = ababa abab i = 5
aba baabab j = 3 不合，故j=F(j)
T = ababa abab i = 5
a babaabab j = 1 不合，故j=F(j)
T = ababa abab i = 5
ababaabab j = 0
因為T[i+1]==T[j+1] 所以F(6) = j+1 = 1

T = ababaa bab
a babaabab
因為T[i+1]==T[j+1] 所以F(7) = j+1 = 2

T = ababaab ab
ab abaabab
因為T[i+1]==T[j+1] 所以F(8) = j+1 = 3

T = ababaaba b
aba baabab
因為T[i+1]==T[j+1] 所以F(9) = j+1 = 4

T = ababaabab
abab aabab
結束>w< ~~~~

因此就得到F函數的值了>w< 呀乎\(^o^)/

會求F函數的值也就同時會String Matching了!!!

不知道大家懂了沒=口=a

總之概念大概就這樣囉～～實踐方面就要自己動腦了XD"

---

不懂的還有不懂的話，這裡有我之前寫字串相關演算法的講義....雖然寫很爛啦= =|||
http://w.csie.org/~b99902112/NTUcourse/Chapter8-String.pdf

不然就再說吧XD" 看是問老師問助教還是....喵:p

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.140
※ 編輯: math120908 來自: 118.160.236.217 (03/23 01:10)