经过一天的酝酿思考，我尝试去理解KMP算法的创造过程，最终得出了那么一点皮毛，今天我就来记录一下我的结果吧

首先，介绍KMP算法的详细资料网络上有很多，大家随意google、wiki、百度应该都能找到了。

我这里要讲的不是KMP算法要怎么实现，而是KMP算法的出现过程，这个过程是我自己原创的，不具有任何绝对的说法，重点只是在于帮助自己或者别人理解这个让人难以理解的东西。

下面就是我的思考路径：

首先我们随便找两个字符串，一个称为”主串“，另一个称为”匹配串“，我们的任务就是要在”主串“中找到一段与”匹配串“匹配的子字符串的位置，那么最简单的思路应该是下面这样的：

用匹配串从主串的0位置开始进行字符比较，一直比较到4位置的时候，发现4位置字符并不相等，这时候用匹配串从主串的1位置进行字符比较，同样发现不相等，继续用匹配串从主串的2位置进行比较······整个过程就是通过每次移动匹配串1个位置来重新与主串重新比较。

以上这样一个比较过程就是最容易想到的，但是这样的比较过程效率不高，我相信很多人都知道这样效率不高，但是我们凭什么说这样的效率不高，除非我们给出一个理由出来是吧。下面我就说说我自己得出的理由：当我们发现主串和匹配串的某个字符不相等的时候，这里有一个条件是成立的，就是主串和匹配串中，不相等字符的”前部分串“是相等的，上图中的前部分串就是0~3位置：abab，然而我们发现按照上面这样的比较过程，我们没有利用这个条件，而是忽略它直接进行下一次比较。那么问题来了（当然不是挖掘机到底哪家强？），”前部分串“相等究竟有什么用？下面我用匹配过程图来说明：

整个匹配过程是通过移动匹配串来比较的。如图，第1次匹配失败的时候，移动后的匹配串需要满足一个前提条件才能继续同主串的4位置比较字符（这里有人会想，我下一次匹配不是跟主串的4位置比较字符，而是主串的1位置啊。那你跟1位置比较字符的时候，到后面是不是同样需要跟4位置比较字符），这个前提条件就是移动后前串（前串：匹配串头部到匹配串失配字符这一串）中的头串（头串：从匹配串的头部算起到任一位置）必须同主串的前部分串相等，只有相等了，我们才有必要继续比较4位置。所以，我们看的出第2次匹配这个过程是没有必要的，因为匹配串ababc中b的头串为”aba“，而这个头串肯定不会跟主串4位置的前部分串"···b”匹配，因为这2个串的最后一个字符都不相等，用下图表示为：

所以，第2次匹配是没必要进行的步骤，现在我们来看看第3次匹配，第3次匹配是匹配串ababc中a的头串为“ab"，而这个头串恰好能够跟主串4位置前部分串“···ab”匹配，用下图表示为：

到此为止，我们思考路径是这样的：第3次匹配满足了前提条件，所以我们才有必要进行主串4位置的比较。

匹配失败时，我们发现该位置继续匹配的前提条件：移动后匹配串的头串必须同主串的前部分串相等

↓

从而发现中间有一些匹配过程是没有必要的

↓

如果我们能够找到一段匹配失配字符前部分串的头串话，那么我们就可省去中间这些不必要的匹配过程，直接用头串的下1个位置（下面我们称为下一匹配位置）与主串失配位置比较。如果相等，那么继续比较；如果不相等，那么同样找到当前失配字符前部分串的下一匹配位置与主串失配位置比较······

↓

到这里，问题就转化为：

在匹配串中，找到失配字符的下一匹配位置，使得头串匹配失配字符前部分串，且这头串长度最大（下面我们称为最长头串），才能保证向右移动的距离不会过大，避免造成遗漏的情况。

↓

这个问题的求解就跟主串没有任何关系了，只跟匹配串自身有关，因为我们是在匹配串中找失配字符的下一匹配位置。

↓

只要找出匹配串每个字符的下一匹配位置，那么我们就解决了在匹配主串失配时该如何移动的问题，提高效率。

到这里，我们的目标也就是找出匹配串中每个字符的下一匹配位置。

【注：至此，先理解以上内容，再看我的下一篇文章：KMP的自我思考之路（二）】

以上所写均是我个人的理解，有任何建议或者意见，欢迎大家跟我一起讨论

KMP的自我研究之路（一）