KMP算法

     之前看了很多关于KMP算法的资料，可能因为我的理解能力问题，大多数感觉都比较晦涩，后来还是决定自己看书然后总结出来一个通俗易懂的办法去解释KMP算法。KMP算法和朴素模式匹配算法相比，其优势在于较低的时间复杂度。因为朴素模式算法很多时候会重复一些没有必要的工作。比如串1：abcdef和串2：abce进行匹配，朴素模式算法的匹配思路是依次进行比较。其实我们直接观察可以看出来串2中abc（前三项）并没有一致的部分，也就是说，如果串2前三项和串1的前三项匹配一致，就能说明串2的第一项不可能和串1的2、3项匹配一致，在这个时候，我们就没有必要再去进行匹配，然而朴素模式算法的匹配思路是依次向后移动进行匹配，这样的话其实程序就会做一些无用的工作，从而影响程序运行的效率。

       KMP算法是对朴素模式算法这一缺陷的改良，使程序可以跳过不必要的运行过程，从而提高程序的效率。

      比如下图中的这个匹配：

      如果按照朴素模式算法，那么我们的下一步是：

 

      接下来依次往后移动，依此类推。然而我们曾经说过，abc这三个字母并不相同，因此如果a-a、b-b、c-c均匹配，只有d-e不相匹配的话，我们就没有必要再重复匹配a-b、a-c了，在这个步骤是没有意义的。我们只需要知道a和e不同，而e与d不同就可以了。因为计算机不是我们，所以虽然他知道这些不一向，但是他无法直接判断a和d是否相同，因此按照KMP算法的思路，我们下一步直接用匹配d-a就可以了，前面两步可以省略。

        所以我们的下一步变成了这样（KMP算法）：

        这是朴素模式算法经历3步以后才能到达的过程，试想如果我们用aaaaaaaaaaaab与aaaaaab进行匹配的话，KMP算法是不是比朴素模式算法能节省出更多的时间呢？而且我们可以发现一个事，就是如果我们用较短的字符串A与较长的字符串B比较，其实比较的次数多少取决于A而并非B，因此我们想要缩短匹配所用的时间就要在A上下功夫了，而指导回溯位数的就是著名的next数组。

        但是怎么去推导KMP算法的next数组？这里不得不先解释一下next数组。next数组的用途简单的来说就是指导计算机回溯位数的数组，它的推导方法的代码用C语言写的话是这样的：

     我们用一个表格来模拟一下数组的变化情况：

 

     （第一行为字符串，第二行为i的值，也就是字符串都得个数，第三行为next数组的值，即j=0）

     a前面没有可比较的字符，因此next为0，

     i=1；j=0时，事实上，前缀后缀都是它本身，因此为1，这时个人的理解，如果不求原因，第二位固定是1，然后执行++i和++j，这一步运行以后，i=2指向b，j=1赋值给next[2]。

      接着我们进行第三步，我们可以发现T[i]和T[j]指向的字符不一致，也就是说j要回溯到T[j]的next，这时候j=1，T[j]的next即T[1]的next，也就是0，然后再进行循环运算，满足的j==0的条件，这个时候，++j，++i，因此next[3]=1，j=1，i=3。

      接着第四步，我们比较T[3]和T[1]的字符，a-a，满足条件，因此++i,++j，这时next[4]=j=2，i=4。

     第五步，比较T[4]和T[2],即a-b，不满足条件，这时候j要回溯到T[j]的next，也就是j=1，然后我们发现T[1]与T[4]比较，是a-a满足条件，这时候++j，++i，i=5,next[5]=j=2。

     依次类推，然后我们最后得出的结论是

     有兴趣的话可以自己去实现一下后三位的数字。

     我们用程序输出检验一下结果：

     这就是KMP算法的使用过程，希望可以给大家一些帮助。

     这是我第一次在****上写博客，如果有问题的话还请大家指正。我是文科生，因此编程主要是自学的，还希望前辈们不吝赐教，有一起自学编程的小伙伴，我们可以一起努力！加油~