KMP算法

在字串匹配领域，有个叫KMP的神算法非常牛x，但是网站和书本的作者介绍这个算法的时候，都会患上临时装逼症，数学推导和概念满天飞，唯恐听者觉浅。由于企业面试应聘技术岗位的应届生经常喜欢考字符串处理，自己平时也常用，因此打算用人话来说一遍。

先抛出问题：给定一个字串，比如"ABABBABAABBA"中，查找"ABAAB"，如果是你，你会怎么匹配呢？

不考虑任何效率的问题，当然就是从头到尾比较过去了，比如：

ABABBABAABBA ABAAB→

比较下来，发现从第4个字符开始不同了，那没办法，说明前5个字符不是我们想要的字串，接下来我们就让字符串往前拱一步，继续比较：

ABABBABAABBA ABAAB→

这一轮更惨，第一个就栽了，没关系，继续死磕往前拱：

ABABBABAABBA ABAAB→

这一轮也不咋滴，比较到第3个就歇菜了。只要我们有毅力，这个过程坚持不懈，总能找到（或者找不到）答案。

现在的问题是：有没有更快的方法来找到匹配的字串呢？

KMP算法的核心意思就是：当我们发现一次比较下来字串没有完全匹配的情况下，下一次的比较也许可以不止往前拱一步，也许可以拱N步，关键是，究竟可以拱几步呢？

搞清楚这个问题前，先来搞清楚一个关键信息：“部分匹配值”，官方的解释太啰嗦了，我掰开了揉碎了讲给你听，就是这样：将我们要匹配的字串写出来，写两遍：

ABAAB→ ←ABAAB

看到了吧，我们让他们一个向左一个向右，相向而行。算一下上一行的右边跟下一行的左边，最多能有几个字符是重合的（注意上一行的首字符不参与这个游戏，否则每个字串都是从头配到尾，就没意思了），这个数值N就是字串ABAAB的所谓部分匹配值，当然，你会发现此时N等于2，因为：

ABAAB→ ←ABAAB

下边的字串再往前走，再也找不到更多的重合的字符了，因此字串"ABAAB"的部分匹配值为2，记为：

ABAAB 2

来，继续算部分匹配值，接下来缩短一点，将最右边的B去掉，来看ABAA的部分匹配值：

ABAA→ ←ABAA

显而易见，字串"ABAA"的部分匹配值是1，记为：

ABAAB

1 2

不断重复上述过程，将每一个字串的“部分匹配值”都算出来，就是所谓的部分匹配表，如下所示。

ABAAB

00 1 12

好了，花开两朵各表一枝，说回刚刚提到的问题：发现不匹配之后，究竟要向右拱几步呢？答案是：可以往前拱 (N-x) 步。N指的是匹配的字符数，x是部分匹配值，现在我们再把刚开始的步骤再做一遍：

ABABBABAABBA ABAAB→

比较下来发现有3个字符匹配，此时N=3，查表得知ABA的部分匹配值x=1，因此我们此时可以往前拱 （3-1）步，接下来比较：

ABABBABAABBA ABAAB→

你发现，此时我们就跳过了一些比较循环，让我们整个算法的效率得到极大的提升。其实KMP算法的核心，就是充分利用比较过的未能匹配的字串的信息，而不是一股脑将他们丢弃。

看到这里的都是有理想的真爱！祝你们洪福齐天！顺便点个分享散播技术正能量鼓励鼓励呗~