KMP & BM
唔，真有趣的 string matching algorithm。
Knuth-Morris-Pratt（KMP）的演算法平均起來和 Boyer-Moore（BM）差不多，有時還比較慢。可是為什麼比較難看懂呀…..
先小記一下， KMP 有用到 prefix function（這是楓葉書(1)寫的，有的是叫做 failure function），然後字串比對是由左到右比；BM 用到的是 bad character heuristic 以及 good suffix heuristic，不過在某些情況下，只用 bad character 就很夠快了，它的字串比對是右到左比。
搜尋時間複雜度：KMP 是 O(n+m)；BM 是 O(nm)，不過最快情況是 O(n/m) 。看起來好像 KMP 比較快對不對？可是剛好相反，至少我手上的 paper 都是這樣。
有空再來寫完整一點的好了。
- Introduction To Algorithms, 2nd. p.923~p930[back]
