1.暴力法
2.KMP(Knuth Morris Pratt)演算法
3.BM(Boyer Moore)演算法
4.Rabin Karp 演算法
今天針對KMP(Knuth Morris Pratt)演算法做註解分析：
題目：
使用KMP（Knuth, Morris, Pratt）快速字串比對演算法找出字串裡面是否包含有某子字串。輸入字串datedadatete與子字串datdadatdatt，請完成此演算法所需之failure function F(i)。
解法：
失誤函數以P為樣本來製作
故用子字串datdadatdatt做失誤函數
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
得到：答案
i
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
F(i)
|
-1
|
-1
|
-1
|
0
|
1
|
0
|
1
|
2
|
3
|
4
|
2
|
-1
|
重點摘要：
KMP演算法的關鍵在於建構一個部分相符表格，好用來計算比對字串位移的大小。由於我們是在比對失敗時，才參考這個表格，所以此表格又被稱為失誤函數。
失誤函數以P為樣本來製作
當
next[1]=0
a
|
?
|
?
|
?
|
?
|
?
|
|
a
|
b
|
c
|
d
|
a
|
d
|
next[2]=0
a
|
b
|
?
|
?
|
?
|
?
|
||
a
|
b
|
c
|
d
|
a
|
d
|
||
next[3]=0
a
|
b
|
c
|
?
|
?
|
?
|
|||
a
|
b
|
c
|
d
|
a
|
d
|
|||
a
|
b
|
c
|
d
|
?
|
?
|
||||
a
|
b
|
c
|
d
|
a
|
d
|
||||
a
|
b
|
c
|
d
|
a
|
?
|
||||
a
|
b
|
c
|
d
|
a
|
d
|
||||
當字元比對失敗在P[j]，而且P[j-k]…P[j-1]正好等於P[0]…P[k-1]時，我們可以得到next[j]=k
如下圖所示：
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
a
|
b
|
c
|
d
|
a
|
?
|
||||
a
|
b
|
c
|
d
|
a
|
d
|
P[j-k]…P[j-1]-> P[5-1]…P[5-1]
P[0]…P[k-1]-> P[0]…P[1-1]
next[j]=k-> next[5]=1
KMP的基本運作原理：
用P(abcdad)比對T
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
|
T
|
a
|
b
|
c
|
a
|
b
|
c
|
d
|
a
|
b
|
a
|
b
|
c
|
d
|
a
|
b
|
c
|
d
|
a
|
d
|
P
|
a
|
b
|
c
|
d
|
a
|
d
|
|||||||||||||
Shift=3
|
a
|
b
|
c
|
d
|
a
|
d
|
|||||||||||||
Shift=4
|
a
|
b
|
c
|
d
|
a
|
d
|
|||||||||||||
Shift=2
|
a
|
b
|
c
|
d
|
a
|
d
|
|||||||||||||
Shift=4
|
a
|
b
|
c
|
d
|
a
|
d
|
|||||||||||||
------------------------------------------------------------------------------------------------------------
參考文件：
1.維基百科
2.網路投影片
3.考選部高等考試三級
4.C語法表示
沒有留言:
張貼留言
如果久久沒有反應，請直接寄信
應該是我不太會用google blogger 導致有留言過久未處理><
實在深感抱歉..