KMP算法是用来解决字符串匹配算法的。例如给定一个主串T，判断其中是否出现了模式串P，即P是否为T的子串。例如：主串T为“hello”，模式串P为“el”，那么P就是T的子串；若模式串P为“elo”，那么P就不是T的子串。
暴力法解决字符串匹配思路很简单。从主串的首字符开始匹配，如果匹配失败，则从主串的第2个字符开始匹配，以此类推。由于思路简单，直接上代码。
int brute_force (string s, string p) { int s_len = s.size(); int p_len = p.size(); if(s_len<p_len)return -1; if(s_len==0)return 0; for(int i=0;i<s_len;i++){ int s_index = i; int p_index = 0; while(p_index<p_len){ if(s[s_index]==p[p_index])s_index++,p_index++; else break; } if(p_index==p_len)return i; } return -1; }如果主串的长度为m，子串的长度为n，那么显然时间复杂度为O(m*n)。
KMP 暴力法的问题在每次与子串比较的过程中，比较了前面的若干位后才比较失败，然后比较主串的位置后移1位，再从头比较。这个过程中的一个明显的问题，就是即使前面的比较失败，但是前面已经匹配了若干位，这些信息并没有帮助到后面的比较，而KMP就是要利用前面比较失败的信息，简化计算。(话是这么说，但是KMP利用的方法还是比较复杂的，在后面会慢慢讲解)
前后缀最长公共元素长度给定一个字符串，如果存在一个尽可能长的前缀，使得。简单点说，如下图字符串ababa，前缀aba和后缀aba相等，而且是最长的相等前后缀，因此字符串ababa的“前后缀最长公共元素长度”为3。
那这个值有什么用呢？它的作用就是KMP的核心思想。
先看一个匹配的过程
主串和子串在红色的位置失配，那子串该怎么移动呢？使子串的前缀aba对其主串的后缀aba。如下图
因此“已经匹配的字符串长度”-“前后缀最长公共元素长度”=“失配后子串需要右移的位数”。
综上，有了这个值以后，就知道如果子串“失配”后，子串应该移动多长才能再次与主串对齐；(注：有了这个值的话，也就有了前缀最后字符的位置，这个位置会在求解next数组时用到)
next数组的由来如果你之前看过一些KMP的介绍，那么一定听说过next的数组，现在介绍一些next数组的来由。还是假设子串为“ababad”，那么有
由于每一个数字是用来确定如果其后面的数字“失配”，那么如何使子串对齐主串的，而且子串最后的字符其后面已经没有字符了，因此其“前后缀最长公共元素长度”值，没有任何意义。
这样，如果每次“失配”后，就去取前一个字符的“前后缀最长公共元素长度”。显然，这样比较麻烦，不妨将整个“前后缀最长公共元素长度”右移一位，而且由于末尾的值没有意义，右移一位后丢失了也没有影响。而右移后的就是next数组。如下图：
这就很好的解释了next数组的意义。
next数组的使用现在来讨论一下，next数组使用的细节。先前只说通过next数组来重新对齐，但其实对齐后，仍然会从主串的“失配”位进行比较，只是子串比较的位置变了。子串比较的位置应该是前缀的后一个字符，而由于next指出的是前缀的长度，那么next的值其实就是前缀后一个字符的位置。综上，“失配”后，主串的比较位置不变，子串的比较位置就是对应的next值（这部分会体现到之后的代码当中）。
next的数组的计算之前只说了如何使用next数组，但是如何高效的获得next数组呢？首先，next[0]=-1,next[1]=0是必然的，之后就是希望递推的使用已知next求未知next。如果已知next[j]=k，那么next[j+1]为多少呢？
因为next[j]=k，那么前缀最后一个字符之后的字符显然为(前缀为：)。如果，那么显然next[j+1]=k+1。下图是一个这种情况的例子，
红色的框代码前缀，篮色的框代表后缀，此时对应的next为2，如何判断最后a的next值(这里指没有右移的)，就需要判断“红色箭头”和“蓝色箭头”指向的字符是否相等，如果相等那么其next值是之前next值加1，也是就2+1=3。
如果呢？那么应该寻找更短的公共前后缀，先看下面的例子
由于b≠d，那么我们可以将前缀aba（红色的框）再细分前后缀，细分后的前缀为红框中的第1个a，这个就是我们要找的更短的公共前缀，结果如下图；
如果此时，“红色箭头”和“蓝色箭头”指向的字符相等，那么其next值为2。但是在我们的例子里，仍然不相等，因此需要再细分前后缀，但是只有一个元素，无法再分，因此我们的例子里d对应的next值为0。
重新整理下，如果，那么就将前缀再细分前后缀，然后比较和更短前缀后一位是否相同，如果不同就继续细分。而这个细分的过程，其实就是不断的递归next[k]。例如将前缀第1次细分，则比较的位置就变为了，然后比较与，如果仍然不相等，则比较与，以此类推。
直观上来看，就是匹配前缀，匹配前缀的前缀，匹配前缀的前缀的前缀，…，直至匹配成功。
C++实现这里以LeetCode第28题为例，这个题就是标准的字符串匹配。
class Solution {public: int strStr(string haystack, string needle) { if(needle.size()>haystack.size())return -1; if(needle.size()==0)return 0; vector<int> next = getNext(needle); int index1 = 0, index2 = 0; // index1是haystack的游标，index2是needle的游标 while(index1<haystack.size()&&index2<needle.size()){ if(haystack[index1]==needle[index2])index1++,index2++; // 如果匹配则继续 // 首字符未匹配 else if(next[index2]==-1)index1++; // 如果不匹配，从前缀的后一位继续进行匹配,next执行前缀后一位 else index2 = next[index2]; } // 如果index2==needle.size()说明匹配完成，此时在haystack中匹配的首位置为index1-index // 否则，匹配失败 return index2==needle.size()?index1-index2:-1; } vector<int> getNext(string needle){ int size = needle.size(); vector<int> next(size); if(size==0)return next; if(size==1){ next[0] = -1; return next; } next[0] = -1; next[1] = 0; // next[i]是字符串needle[0]到needl[i-1]中前缀之后的第1个字符， // 这个字符也是求下一个next需要进行比较的字符，这里定义这个字符的下标为prefix for(int i=2;i<size;i++){ int prefix = next[i-1]; // 求next[i]，其实是在求needle[0]到needle[i-1]的最长公共前后缀长度 // 递归寻找needle[i-1]==needle[prefix] while(prefix>=0&&needle[i-1]!=needle[prefix])prefix = next[prefix]; if(prefix==-1)next[i] = 0; else next[i] = prefix+1; } return next; }};