今天又看了一遍KMP,感觉真的懂了...就来这儿发一下心得吧.

KMP算法其实就是暴力的改进版.让我们看看暴力的匹配.

Original string: ababababcbbababababcPattern string:  abababc

步骤:

ababababcbbababababcabababc
....中间一些步骤
ababababcbbababababc
abababc
这里a和c匹配不了了,传统的作法会从第二个字符`b‘开始匹配.明显不行又跳出.即:
ababababcbbababababc
 a...
再从第三个字符`a‘开始:
ababababc...
  abababc
现在匹配了.继续重复.

很明显这个算法在极端情况下的时间复杂度是$\text{O}\left( len\left( \text{Orig String} \right) \cdot len\left( \text{Patt String}\right)\right)$.效率很低.

想一想.在Brute Force中,每次失配后都会将Pattern的头指针指向下一个字符匹配,相当于每次失配都只能跳过一个字符.显然这么做效率非常低.能不能一次跳过多个字符却依然不会漏过匹配呢?当然可以.这样跳过的要求是什么呢?

看看这个例子:
ababababc
abababc
首先`a‘和`c‘不匹配.跳到`b‘么?明显不行,不匹配.
注意到模式串中的
abababc
最前面的`ab‘和无法匹配的`c‘前面的`ab‘是相同的.

KMP算法心得