2008年11月10日 星期一

[Algo] String Matching - KMP Algorithm

看了兩次,可是每次都忘記,所以做個筆記
s: input string
p: pattern

Failure Function的值k,就是下次要從p(k)開始matching

舉例

Pattern A B C A B C D
failure -1-1-1 0 1 2-1

Case I:
Input string
ABCDADFGACEDAABBBB
ABCABCD

紅色=not matching
step1: 看最後一個matching字元 (綠色的字) 的failure function value= f
step2: 將p(f)對齊綠色的位置 ( p(i)代表p的第i個字元 )

ex. f(C) = -1 ,所以p(-1)對齊上面那排的C
ABCDADFGACEDAABB
>>>ABCABCD

Case II:
ABCABCEACAADDBBBABCABC
ABCABCD

f(C)=2 ,所以p(2)對齊上面那排的綠色C

ABCABCEACAADDBBBABCABC
>>>ABCABCD


講的不是很有條理,不過我先給自己看懂就好= =
改天再來整理的清楚一些