[Algo] String Matching - KMP Algorithm
看了兩次,可是每次都忘記,所以做個筆記
s: input string
p: pattern
Failure Function的值k,就是下次要從p(k)開始matching
舉例
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
Case II:
ABCABCEACAADDBBBABCABC
ABCABCD
f(C)=2 ,所以p(2)對齊上面那排的綠色C
ABCABCEACAADDBBBABCABC
>>>ABCABCD
講的不是很有條理,不過我先給自己看懂就好= =
改天再來整理的清楚一些
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
講的不是很有條理,不過我先給自己看懂就好= =
改天再來整理的清楚一些
Asdaninclas-fu Ian Parra https://wakelet.com/wake/VpjRSDZ7TBye3EoMHaXS2
回覆刪除talnerssandsund