笔者在学习算法的时候常常习于揣度设计者的思路，在笔者看来，KMP算法背后的思想简单，但很有趣。它折射出了人们设计算法时一种较为普遍的思想，因此值得一提。
要想读清楚KMP算法，我们需要先了解两件事，一件事是在KMP算法前，作为KMP算法的优化对象的BF算法，另一件事则是它们希望实现的目标。
从第二件事说起，无论是BF算法，还是KMP算法，实际上都希望实现这么一个功能，那就是在给定一个主串，然后给定另一个串（我们为了方便和易于理解称其为模式匹配串）后，在主串中找到这一模式匹配串。我们称这一过程为模式匹配。
在这一目的下，BF算法用一种笨拙的方法实现了模式匹配，它的匹配方式是这样的：
- 对于主串abaabbc，模式匹配串abc来说，先将模式匹配串的第一个字母a与主串的abaabbc中的第一个字母a匹配。
- 匹配成功，将模式匹配串中的第二个字母b与主串中的第二个字母b匹配。
- 匹配成功，将模式匹配串中的第三个字母c与主串中的第三个字母a匹配。
- 匹配失败，再将模式匹配串中的第一个字母与主串中的第二个字母b匹配。
- ……
在这个过程中，我们为每个串分配一个指针，用以指向对应的字符进行匹配。我们发现，在BF算法中，一旦匹配失败，我们马上将模式匹配串的指针复归到首个字符上，然后将主串的指针从原来的首个字母处向前进一位。
不难发现，这个办法虽然毫无疑问可以达到匹配的目的，但是这中间产生了许多的信息浪费。比如，我们既然明白abc三个字母各有不同，在比到c的时候发现不对，为什么我们还要继续从主串的“b”字母处开始对a做比较呢？在已经知道前面匹配成功，而模式匹配串中字母各不相同的情况下，直接从这一个不是c的字母开始对a进行比较，不是更好吗？
笔者看来，KMP算法正是基于这样的一个思路，为了提高在比较过程中对已有信息的利用率而设计的算法。我们思考，对于模式匹配串而言，在比较到任何一个字符的时候，我们都已经拥有了前面所有的字符已经发生匹配这一信息，既然如此，我们就希望通过对前面的字符进行一定的解析，来得到在任意一个字符发生不匹配的情况时，到底应该从哪个字符开始重新匹配。
我们来分析几种情况：
- 对于模式匹配串abcdefg而言，任意一个字符不匹配的时候，由于这个串中所有的字符都是互不相同的，因此直接在不匹配的字符处跳转到第一个字符开始匹配即可。也就是说，对于任意一个字符，它们的跳转位置都是“1”。
- 对于模式匹配串abcdabce而言，对于前四个字符而言，由于互不相同，在不匹配的时候，直接跳转到第一个字符处即可。他们的跳转位置是1，而对于后三个字符而言，则存在着一些有趣的不同。对于第五个字符a而言，虽然它与首字母相同，但是不匹配的时候仍然跳转到a，因为它前面的字符都是截然不同的。你可能会想，既然这一个字母和首字母相同，那么这时将首字母拉过来匹配不是注定不同么？为什么我们不直接在这种情况下从后一个字符开始对a进行匹配？原因很简单，因为在整个处理过程中，只有在字母和首字母相同的时候可能会存在这种情况，既然如此，为它额外添加一个处理方式其实是没有太大必要的。对于模式匹配串的倒数第二个字母b而言，我们观察到，由于它的上一个字母是a，因此在两个字符串的比较中，我们已经得到了一个相同的字母a，这个时候，我们没有必要把a拉过来比较了，而是可以直接把第二个字母b拉过来比较，也就是说，对于这个倒数第二个字母“b”而言，它跳转的位置不是“1”，而是“2”。对于倒数第三、四个字母c、d亦然，它们的跳转对象是“3”和“4”。
我们会发现，在这个算法的执行过程中，我们通过对于已经比较过的字符的信息的分析，对于每一个字符都分配了一个跳转位置，我们把这个跳转位置和字符一一对应，构建成一个数组，称为next数组。
这也就是说，只要我们想个办法求出next数组，我们在匹配失败的时候就不用像BF算法一样笨拙地跳回去，而是可以原地更换装备，继续前行。这样，在许多的情况下，就提升了比较的效率。
那么，我们该怎么求出next数组呢？根据我们上面的分析，一个字符究竟要跳转到哪里，关键在于它前面的字符串是怎么样的。如果一个字符前面有一个和整个模式匹配串的开端相似的字符串，那么它就会跳转到后面一些的地方，反之则跳转到前面一些的地方。
经过思考，我们提出了这么一种求next数组的算法：
- 对于任意一个字符，将它前面的第一个字符和整个模式匹配串的第一个字符匹配。
- 若匹配成功，则计跳转位置为1，继续向前匹配。若没成功则同样继续向前匹配，
- 将这一字符前的第二个字符和整个模式匹配串的第一个字符匹配，若匹配成功，则将这一字符前的第二个字符后的第一个字符和整个模式匹配串的第二个字符匹配，若再次成功，则计跳转位置为2，继续向前匹配。若没成功，则不计，继续向前匹配。（由于笔者的加入图片功底较差，读者可以自行画出串来跟着这个处理路径观察对应字符来辅助理解。）
- 循环往复，在发现向前已经顶到整个模式匹配串的第一个字符时停止，这时记下最大的跳转位置，这就是这个字符的跳转位置。
求出next数组是KMP算法的关键，在这之后，匹配的时候只要根据next数组跳转就好了。
不难发现，这一算法背后的思想相当简单，为了提高匹配的效率，我们在观察到了信息利用的效率较低之后对其进行了优化，随着一步步的细化，最后得到了KMP算法。事实上，在笔者看来，为了优化、或是实现等目的，对已有的算法和办法进行观察和总结，并找到优化的点，逐步细化，正是许多算法被设计与实现的基础。这也是笔者所以说KMP算法有趣的点。目前笔者接触到的算法不多，还盼望能见到更多更有趣的算法。