【2】KMP算法的一些理解问题
该算法在考研时书上看到过，但是因为不作为必考内容所以没有细细复习。这次复习到才感受到它的魅力，并且也花了很久时间才弄懂了基本概念。
关于KMP的细节不再细说，这里只提出学习的方法和对大家可能遇到的问题的理解：
一、KMP之前
当我们需要在字符串S中找到是否存在P时，是怎么解决的？先看看暴力方法是怎么解决的——因为暴力方法最好理解，符合我们的惯性思维，当然时间复杂度就达到了O（m*n），其中m和n分别代表字符串S的长度和模式串P的长度。
二、什么是KMP
KMP的名字是该算法的三个创始人名字首字母拼成的。从上述我们知道，在迭代过程中其实包含了一些不必要的判断，我们需要寻找到一种算法对不必要的判断进行剪枝。这就是KMP要做的事，它可以把算法复杂度降到O（m+n）
三、如何进行KMP，需要理解的地方
1、理解：字符串移动的长度 = 已匹配的字符长度 - 失配字符上一位所对应的最大首尾匹配长度
什么叫最大首尾匹配长度？例如：123 8547 123 该字符串的最大首尾匹配字符串是123，那么它的最大首尾匹配长度就是3，为什么需要这个数字后面再解释。
2、 理解：next[k]数组是求解的关键
3、KMP算法的流程：先求出next数组，再进行匹配运算
四、几个问题：
1、字符串移动的长度 = 已匹配的字符长度 - 失配字符上一位所对应的最大首尾匹配长度，这个公式的本质是什么？
本质在于：已匹配的字符串实际上已经传达了一些匹配的信息。试想一下，如果已经匹配了12345x中的12345，到x位时失配，按以往的方式就要从2开始匹配，但实际上2—5都是不用判断可直接跳过，为什么？因为12345没有存在首尾匹配的字符串。但是，如果已经匹配了1234123x中的1234123，到x位时失配，那么应该从下一个123开头去匹配，也就是从123x……这样的串开始匹配。如果我们都知道了模式串的最大首尾匹配字符串的信息，那么每次就可以跳过相当的字符串进行匹配操作了。这也就是next的意义。
2、在计算next时，为什么不匹配时要执行 k = next[k]？
这个问题感觉是最疑惑的，目前只是大致理解，感觉不好用文字表达...
五、还有优化空间么？请看参考博客：
从头到尾彻底理解KMP http://blog.csdn.net/v_july_v/article/details/7041827（详细）
KMP算法 http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html（简单易懂）
字符串匹配算法KMP http://kb.cnblogs.com/page/176818/（中等理解难度）
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
