在所有的字元串匹配演算法中,KMP 演算法是最知名的,實際上,它和 BM 演算法的本質是一樣的。
1. KMP 演算法基本原理
KMP 演算法是根據三位作者(D.E.Knuth,J.H.Morris 和 V.R.Pratt)的名字來命名的,演算法的全稱是 Knuth Morris Pratt 演算法,簡稱為 KMP 演算法。
KMP 演算法的核心思想和 BM 演算法非常相近,就是在遇到不可匹配字元的時候,我們希望能將模式串向後多滑動幾位,跳過那些肯定不會匹配的情況。
在 KMP 演算法中,我們從前向後對模式串和主串進行對比,不能匹配的字元仍然叫作壞字元,而前面已經匹配的字元串叫作好前綴。