KMP匹配算法的理解
一、介绍
在实际中，我们会碰到字符串的模式匹配问题。
最常见的就是给定一篇文章，查找出特定单词的首位置。
可以把问题简化成，针对一个长序列，找出与特定字符串匹配的位置。
如长序列：abcdabcdeeeegd，查找字符串为 abcde
最直观的就是暴力匹配法：依次比较两个序列的元素是否相等，相等则继续两个序列的下一个元素比较，否则返回长序列的原位置开始下一个字符与给定单词的开头的比较。
如 abcdabcdeee，与abcde
abcdabcdeee abcde
遇到不相等，开始b与a的比较。
可以看到，当第一次比较不相等时，下一次可以比较长序列中的 第二个a与原序列的a，从而提高效率。
二、KMP匹配算法
KMP算法的处理流程很简单。
1.对要匹配的单词序列，产生一个映射关系，映射关系为：序列的第i个元素→下一个要比较的位置。
其意义是匹配时，如果前面i-1个元素相同而第i个元素不相同，则下一次比较的是，文章序列中不相等的元素与，第i个元素映射位置的比较。
如上面的例子，比较到a与e不相等，找到e映射的位置（如1），则开始文章序列中的a与单词序列的第一个元素的比较。
整个比较过程，文章序列的比较位置是一直向前，不会回头的；而单词序列的比较位置则是不停往返。这与暴力法是相反的。
2.开始比较。比较过程如上面所述。
整个算法中最核心的就是产生单词序列与下一个要比较的位置的映射。
针对单词序列每个元素都不同的情况，如abcd。如果比较到d时，发现不相等，那么下一个要比较的是什么呢？
直到d才不相等，也就是说abc与文章序列是一样的。下一个要比较的自然就是a，也就是重头开始比较。
如果是abcabe呢？比较到e的时候发现不相等，下一个要比较的是什么？
e才不相等，也就是说abcab与文章序列相同，下一个要比较的就应该是c了。理由如下：
文章序列可以推断出为abcabx（x表示未知，但不为e）。按照常理，下一个要比较的自然就是
abcabx
abcab
也就是比较x与c是否相等。
从这个情况看到，需要找到已经相等的元素中（也就是x之前序列，也就是第二个b前面的序列），以首元素为开始的连续子序列重复出现的位置。如果没有，则从第一个元素开始比较。
如果是abcabeg，在g的时候不相等。
按照前面的规律，应该是比较e与c。但明显，根据前面元素相等，可以知道e的位置就是e，也就是说出现abe而不是abc，故不需要比较e与c。真正的做法是，截取不相等的元素前面的序列（如abcabe），找到以首元素开始的连续子序列，与最后元素为e的连续子序列相等的部分，再比较；如果没有这样的子序列，则冲第一个元素开始比较。
截取自《大话数据结构》
如abcabe，在e的时候不相等。看abcab序列，结尾元素为b，开头元素为a，找到开头子序列ab，与末尾ab子序列相等，故下一个比较的就是e与c。
又如abcabeg，在g的时候不相等。看abcabe序列，没有找到以a开头的，e结尾的前后两部分相同的连续子序列。所以比较g与a。
三、产生映射关系的代码（截取自《大话数据结构》）
先来说明一下next[i]元素的含义。其意义就是前面 1,2,...next[i]-1 = i-next[i]+1,...,i-1 元素，但i元素与next[i]元素的关系还未知。
程序是从沿着单词序列依次找到各个元素对应的下一个比较的位置。i是逐渐+1，也就是沿着序列逐个查找。j则是找到对应子序列相同的部分的序号。
我们先沿着程序部分走一遍。进入到while部分。j=0满足，next[2]=1。第二个元素前面只有第一个元素，所以当第二个元素不相等时，与文章序列比较的就是第一个元素。
如果第2个元素与第一个元素相等，那么当第三个元素与文章序列比较失败时，就知道前面两个元素相同，所以要比较的就是文章序列和第2个元素，即next[3]=2.
如果操作进行到第i和j个元素不相等了（也就是对于前面的i-1个元素都已经找到了对应的下一个比较位置），就进行j值回溯。
这部分是什么意思？
我们先想一下不等的时候。这个时候已经知道了，前面
1,2...j-1元素 = i-j+1, ...,i-2, i-1元素
j元素 != i元素。
现在的问题就是找到前面 1,2,...a-1元素 = i-a+1, i-a+2,...i-1元素，同时 a元素 = i元素.先来判断a的范围，要满足a的条件，则a<j
（因为第j个元素不等与i元素，但a元素等于i元素； 且序列都是从第一个元素开始，a是j的子序列）。
所以问题是：
找到1,2,...,a-1元素 = j-a+1,..,j-1元素（利用已知的j与i的关系进行替换），这就是next[j]的含义
同时满足a元素=i元素。
综合得到只需要判断next[j]元素是否等于i元素即可。
上面的程序采自《大话数据结构》
如果错漏，请指正！