许久没有写随笔了，是时候把东西整理下。
KMP算法-基本优势：大家都知道该算法是用于字符串匹配的时候的，它的时间复杂度可以达到O(n+m)，(n,m为两字串的长度)这个而我们如果凭直觉来写的话我们应该会逐字匹配，匹配不了就移
到下个字符继续匹配，这样走下来的话时间复杂度就会是O(n*m).
参考翁惠玉老师的数据结构：题解与拓展，以下是我对其中KMP的理解。
套用书上的例子：
假设有两个字符串A(len:n),B(len:m). KMP算法用两个变量i和j分别表示A串中从A[i-j]到A[i]的子串与B串从B[0]到B[j]子串完全相等。
假设A = abababaababacb B= abacb
i= 0 1 2 3 4 5 6 7 8 9
A=a b a b a b a a b a--
B=a b a b a c b
j= 0 1 2 3 4 5
可以看到当j = 4时两子串匹配满足A[i-j]到A[i]的子串与B串从B[0]到B[j]子串完全相等
但j=5就不等，这就要让j继续回退到一个较小值jb,尽可能地让这个值变得最大，同时又满足B[0]-B[jb]与A[i-jb]-A[i-1]继续相等。还是举例比较好：
A = ababab```
B = ababac```
可知之前匹配部分都相等，这样一来问题就变成尽可能少的移动B使得A与B在i=4的位置下有最大重合```后继续匹配，这样问题又变成如何移动B使得B*与B在i=0-4有最大重合，这样就转换B自己的问题了。就是在i=4找到B*的前缀与B的后缀有最大重合。
这部分可以参考http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
假设next[j]是移动B使得B*与B在i=0-4最大重合，当j<=i时也就是B[0]-B[j]与B[i-j]-B[i]重合部分最大
之后我们又出现一个函数p[j]来记录这个位置也就是这时的j值，p[j]=i-next[j]+1.表明p=x表明这个位置B的前缀们与后缀们有共同项最大长度x
之后问题来了，如何计算每个p[j]呢？
还是举例哈：对于前面B=“abababc”，假设我们已有
0 1 2 3 4 5 6
B=a b a b a c
p=-1 -1 0 1 2 ?
如何求p[5]位置呢? p=-1表明这个位置B的前缀们与后缀们木有共同项.
已知p[4]=2，也就是B[0]-B[2]与B[4-2]-B[4]重合，我们合理的猜想应该是B[p[4]+1]要是也与B[5]重合，那我们就得到p[5] = p[4]+1啦。
可惜这里B[5]!=B[3],所以我们要往前再找(这里是理解的难点，我们需要往前多少？：前缀的前缀)。 为何呢？ 要发现B[4]位置总是会出现在B[p[4]]位置，然后是B[p[p[4]]]位置。而我们只需要判断的是B[5]是否与这些位置的下一位相等即可得到p[5]的值了：p[4]+1，不是，那就下一个猜想p[p[4]]+1，还不是，那继续递归。这是一个递归的过程，前缀的前缀。····
所以这个p[x]的函数过程是
p[0]=-1; //默认的 for (int I = 1; I < len(b); i++) { j = I – 1; //而我们只需要判断的是B[5]是否与这些位置的下一位相等即可得到p[5]的值了：//p[4]+1,不是，那就下一个猜想p[p[4]]+1,直到跳出循环 while (j >= 0 && B[p[j]+1] != B[i]) {j = p[j]} if (j < 0) p[i] = -1; else p[i] = p[j]+1; }
后面的过程应该也就不难了，
i= j = 0; while (i < size&& j < size) { //逐字比较 if (B[j] == A[i]) {i++;j++;} //若j=0则意味着还没有匹配到首个B[0]与A[i]相等 else if (j == 0) {i++;} //匹配到一半失败后就要从上个最佳匹配的位置下一步再开始匹配 else {j = p[j-1] + 1;} } //匹配好的首位置 if (j == b.size) {return i-j;} else return -1;//说明还没匹配完就遍历完A了，失败。
原文：http://www.cnblogs.com/KiddingJohn/p/5264132.html