分享到plurk 分享到twitter 分享到facebook

版本 fe8ec45d124bfae4b686845b54114b3c9859f539

acm/course/String_Matching

KMP

Knuth-Morris-Pratt algorithm

使用時機: 給定A,B兩字串,尋找B字串是否存在A當中

當B的字串內容,本身有重複的字串時,可用KMP以減少重複否配的時間

ex:

B : aabaab

B字串本身重複 “aab”

跳過重複字串

方法:先用fail function找出字串B重複的字串

Fail Function

目的:當否配失敗時,能知道字串B要對齊哪裡繼續否配

變數:

B [ ] … 存放字串B

pi [ ] … 紀錄前一個重複字串出現的位置

cur_pos … 目前字串重複的位置

初始化:

cur_pos 初始為 -1 pi[0] 初始為 -1

Z Algorithm

Z_value

從第2個element開始以其為字首,去和以第1個element為首的字串比,找出最長相同字串的長度

Z_Box

最長匹配長度,L表示左邊界,R表示右邊界

如何算出Z_value?

在算Z_value時會有3種case 1.自己沒有被別人的Z_Box包住 就乖乖數