网上之所以有这么多版本的KMP算法，是因为有的人写的是最大长度串版本的，有的人写的是next数组版本的（具体区别看下面博文），有的人写的是next优化版的，有的人写的是未优化的，不同人写的循环方法不同，这些写法间的效率是有一定区别的
KMP算法具体讲解看这篇博客，讲的非常非常详细：
https://blog.csdn.net/v_july_v/article/details/7041827#
重点应该在理解Next数组和Next数组的优化
我试着再写一下我理解的优化过程：
比如这张图：
设上面的串为A[]，下面的串为B[]，下标从0开始
根据最大长度串数组C的定义：
当前子串字符之前的字符串中，有多大长度的相同前缀后缀。例如如果C [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。
对于abab这个子串来说，最大长度串数组C就是0 0 1 2，那么next数组（未优化版）就是最大长度值整体向右移动一位，然后初始值赋为-1，即-1 0 0 1。
我们会发现当发生A[3]c与B[3]b失配后，左移两位（3-next[3]）后，会A[3]c会再次与B[1]b失配，事实上这是必然发生的，
回看next数组的定义（其实也就是最大长度串数组）：j 之前的字符串中有最大长度为k 的相同前缀后缀。既然后缀的这个字符已经失配了，那么前缀相同地方的字符也一定会失配，所以要避免这个情况发生，也就是若：B[j] = B[ next[j] ]就要让B[j] = B[ next[j] ]。
总结一下这个过程：
先求出最大长度串数组，整体左移一位，若B[j] = B[ next[j] ]即B[j] = B[ next[j] ]
最后给出一个nenxt优化版本的代码
1 int a[1000005]; 2 int b[10005]; 3 int len1, len2; 4 int Next[10005]; 5 void getNext() 6 { 7 int k = -1, j = 0; 8 Next[0] = -1; 9 while(j < len2) 10 { 11 if(k == -1 || b[j] == b[k]) 12 { 13 k++; 14 j++; 15 if(b[j] != b[k]) 16 Next[j] = k; 17 else//如果这一步失败 那么同值的也会失败 18 Next[j] = Next[k]; 19 } 20 else 21 k = Next[k]; 22 } 23 } 24 int kmp() 25 { 26 getNext(); 27 int i = 0, j = 0; 28 while(i < len1) 29 { 30 if(j == -1 || a[i] == b[j]) 31 { 32 i++; 33 j++; 34 } 35 else 36 j = Next[j]; 37 if(j == len2) 38 return i+1-len2; 39 //返回的是匹配到的index，如果是求次数或对错的话需要修改 40 } 41 return -1; 42 }