给定一段话，如何快速地从中搜索我们想要的单词呢？显然，在有关文字的处理中，这是非常基本的一个问题。
最简单的方法，当然是逐个逐个的比较。具体而言，给定一段长n的文字(text)，记为T[1,2,...,n]；一个长m的单词(word)，记为W[1,2,...,m]。我们固定住text不动，然后把word想象成一把尺子，放在text下面。于是，最初，W[1]对着T[1]。如果W[1]=T[1]，就比较W[2]和T[2]，如果还相等，就继续往后比较；如果直到把W比完了都还没出错，那么我们就正确地找到了这个单词。如果途中任何一个位置不匹配，就说明在T[1,...,m]位置是不可能找到一个单词W了，于是那我们就把尺子往后移动一个单位，然后从头开始匹配。重复这个过程，我们就可以把T中所有的W给找出来。重复到什么时候结束呢？当尺子的右端超出“被测物体”的右端的时候，显然已经不可能找到匹配的的单词了，这个过程就可以结束。
上面这个方法显然是管用的，不过它的效率如何呢？假定T=aaaaaaaaa，10个a；W=aaab，3个a一个b。好了，开始比较：T[1]=W[1]，T[2]=W[2]，T[3]=W[3]，直到T[4]和W[4]，出错了。于是，把word往后一个单位，继续比较：T[2]=W[1]，T[3]=W[2]，T[4]=W[3]，等到T[5]和W[4]，又悲剧了。肿么办？再移一个位置……要按照这样的暴力解法，把每个字母的比较算作一次基本运算，我们得整整进行4*(10-4+1)=28次基本运算。更一般地，对一个长n的text和长m的word，如果运气差到了极点，我们每次放置好尺子W，都得比较到W[m]才能确认当前搜索失败，然后移动一个单位的尺子；这意味着尺子的每个位置我们都进行了m次比较。总共有多少位置能放置尺子呢？显然，在移动word的过程中，只要尺子右端没有超出被测物体，这个位置就是潜在的一个有可能的正确匹配；简单的计算可知，一共有n-m+1个位置。所以，在最坏情况下，我们要做(n-m+1)*m次基本运算。在假定1<=m<=n的情况下，这个数字是O(nm)的。
有没有办法能比较的快一些呢？
考虑这样一种情况。
T = aaaaabqweaaaaabrtyaaaaabuioaaaaabplk
W = aaaaabc
最开始，我们把W和T的左端对齐，然后逐个字母比较。当比较到红色的字母时，不匹配出现了。按照刚刚的思路，我们应该把W右移一个单位，然后重新重头匹配。
T = aaaaabqweaaaaabrtyaaaaabuioaaaaabplk
W = aaaaabc
这回，我们貌似运气不错：T[2]和W[1]相等，T[3]和W[2]相等……可悲剧的是，到了T[6]和W[5]时，不匹配又出现了。没办法，我们只能继续移动W，再次重头开始匹配。重复这样的过程，我们最终会发现，在T中是找不到W的。
上面这个例子还好说，毕竟text只是由4个6+3(aaaaab+另外三个字母)组成的，总长度不过36。如果它是由10个6+3(假定这些6+3都不包含W)组成的呢？要是20个、50个、100个呢？我们到底能不能搜索到W=aaaaabc？
想象你正拿着W=aaaaabc这把尺子去和text比对，你其实是周而复始地在把W和aaaaab???做比较。多比上那么几次，也许突然有一天你会发现，如下这种结构：
T = *****aaaaab???*****（前后两部分以*代替）
W = aaaaabc（在c出错）
当在c出错时，是压根不可能通过把尺子W仅仅移动一两个位置就找到和W匹配的单词的。
咦。。。好像真的是哦。。。
为啥呢？
因为原本上下两行都是5a+b；现在W右移了一个单位，下面一行还是5a+b，可是对应上面的位置却被抹去了一个a，变成4a+b，进而3a+b、2a+b。于是，尽管最初的4a、3a仍然匹配，可对比到b的位置时，上b下a互不相等，出错是必然的。
这给了我们什么启发呢？一个很自然的想法就是，在有些情况下，尽管W右移之后我们仍能匹配出个4a、3a来，可是这样的比对纯粹是浪费时间，早晚都会出错。我们完全可以一次性把W右移好多个单位，从而提升我们的效率。可是，在什么情况下我们可以大规模右移？每次大规模右移，我们又该右移多少个单位呢？
答案是：右移到T[k]之前的若干个字母和W词首的若干个字母是匹配的，这种右移才有意义。想象我们的匹配过程，如下图所示：
T = *****????????*****
W = ???????????
W' = ???????????
T[k]位置（红色所示）失配时，我们发现，k前面的4个字母和W词首的4个字母（黄色所示）是匹配的，所以我们可以直接把W右移3个位置到W'，使得黄色部分对齐，然后继续比较T[k]和W[5]就可以了。这样做的正确性很容易说明。想象我们并没有进行大规模移动，而是只按照以前的思路把W往右移动了一个单位到W''，如下图：
T = *****????????*****
W = ???????????
W'' = ???????????
根据刚刚的假设，W和T的蓝色部分并不匹配，那么W''的蓝色部分自然也和T不匹配。虽然部分匹配是可能的，比如下面是5a+b，上面是4a+b，这时还是能对得上4个a；可失配迟早是要出现的，W''必须继续右移。
不过，应当指出，能找到的黄色部分可能不唯一，比如：
T = aaabaaaaccc
W = aaabaaaaa
T = aaabaaaaccc
W = aaabaaaaa
T = aaabaaaaccc
W = aaabaaaaa
上图中，三对黄色都是互相匹配的。此时，我们则应取最长的那一对两两对齐，否则一次性就把W右移了过多，可能会漏掉正确的匹配。
再进一步观察，在遇到红色的?造成失配之前，T和W是匹配的，这其实是说，如果我们重新对上面的图进行着色话，下图中绿色的两部分是相等的。
T = *****????????*****
W = ???????????
而我们刚刚分析中寻找的两段黄色，其实就是上面绿色部分的尾巴与下面绿色部分的开头进行匹配，然后取其中最长的那个匹配。既然上下两行的绿色是相同的，我们完全可以抛开T不看，只对W进行分析。这意味着，失配时W要右移多少，其实和T是没关系的，只和W自身的结构有关。这是一个与人的直觉多少有些相悖的结论，不过前面的分析说明，这个结论是正确的。
至此，我们最初搜索问题的新方法已经有了雏形。首先，我们要对word进行预处理，分析一下在word的每个位置失配时分别应该怎么移动。然后，任凭你给出一段什么样的text，我们还是把word当成一把尺子，和text进行比对。只不过，在现在这种检索中，word是可以大规模移动的。而且，令人兴奋的另一点是，在这种思路中，text的扫描是不走回头路的。如下图所示：
T = *****????????*****
W = ???????????
W' = ???????????
当T在T[k]遇到红色的?失配时，我们要做的只是把W进行移动，然后仍用T[k]与新位置的尺子进行比较。如果匹配，则保持W'不动，上下两行各向后扫描一个字母，比较T和W'的下一个位置；如果失配，则将W'再次进行移动。如果T[k]一直失配，则尺子一直右移，直到最后T[k]和W[1]对齐还仍然失配时，我们才彻底放弃T[k]位置，转而对T[k+1]和W[1]进行比较。注意，在最初那种简单粗暴的算法中，我们一旦出错，text也要回过头去重新扫描的。很显然，现在这种搜索方式比最初那种O(mn)的是要快得多的。具体是的时间复杂度要用到摊还分析，这里就略过不提。
好了，现在我们只剩下最后一个问题，即是如何对word进行预处理，获得最长黄色部分的长度。而这其实就是让我们把word的每一个前缀（头1个字母，头2个字母，头3个字母，...，所有字母）当成一个独立的字符串，然后看看这个字符串的头尾有没有重合的部分。我们给它一个正式的名字，叫做失配函数。考虑到这种重合具有“连续性”，相关的计算并不是太复杂。
啥叫“连续性”呢？举例而言，如果W=?????????*****的第9个前缀子串的失配函数值是3，现在需要计算第10个前缀子串，怎么进行呢？根据失配函数的定义，黄色部分是相同的，所以我们只需直接比较W[4]和W[10]就行了：如果他们相等，就可以和前面的黄色连起来，于是对应于第10个前缀子串的失配函数值就是4。比较麻烦的是如果红色的*和?不相等该怎么办。
幸运的是，我们这里完全可以采取和上面一样的思路，想象成是W在和W自己匹配。回忆我们分析在text中寻找word的过程，每次比对时都意味着T和W有两段黄色对上了，然后比较它们的下一个字符，如下图：
T = ****?????***
W' = ?????????
而我们现在分析的W[10]的情况不也是一样吗？于是，跟之前一样，如果红色的*和?匹配了，那么上下两行黄色各向右生长一个单位。如果不匹配，就让下面的W进行大规模移动，只不过此时的T就是W本身。如下图：
W = ?????????*****
W = ?????????*****
到底怎么移？和刚刚的思路一样，当然是移到首尾重合的下一个位置。以上图为例，我们要做的就是分析word的前3个字母构成的子串的失配函数。
这可太好了。这意味着，所有的失配函数值总是依赖于前面的失配函数值的。给定k位置的失配函数，不妨记为f[k]=p，求f[k+1]，就是比较W[k+1]和W[p+1]是否相等。如果相等，黄色就向前生长1，所以f[k+1]=p+1；如果不等，就说明上图的W与W自身匹配失败了，也就是下面那个W在W[p+1]位置匹配失败。为了移动下面的W，我们要查f[p]是多少，即是f[f[k]]。依此类推，反复递归调用，直到最后到了W[1]，这个过程就结束了。
呼。。。终于写完了。。。这就是传说中大名鼎鼎的KMP算法~