KMP算法是数据结构与算法中串的经典算法案例，KMP是由三位学者同时发现（D.E.Knuth，J.H.Morris和V.R.Pratt），然后就以他们命名的算法。
串的模式匹配
串的模式匹配也就是一种串的定位操作，比如：
提供一个主串T和一个模式串S，需要获得模式串S在T中的位置。
BF算法
BF算法（Brute-Force）顾名思义就是暴力搜索算法，这也是比较容易想到的一种方法。
- 算法首先对S串和T串从首位进行比对匹配
- 如果匹配相同双方同时进行下一个比对
- 如果匹配不相同，S串回溯到本轮比对的开头的下一个数据，T回到开头进行新一轮的比对。
BF算法分析
暴力破解的算法相对简单，这里不再过多讲解算法细节。
值得注意思考的是：
假如主串S的长度是N，模式串T的长度是M。举个最坏的例子，S：aaaaaaaab T：aaaab 不做任何优化的情况下，需要进行至少MN次比对。
所以，该算法的时间复杂度在O(NM)数量级上。
KMP算法
KMP算法提出来就是为了优化暴力搜索遗留给我们的思考。当我们遇到思考题中S，T时，什么时候可以减少回溯？怎么避免不必要的回溯操作？
通过*2图可以引发我们的思考：
当模式串T比对到T1的时候，位置1、2、3分别匹配成功，但是位置4并匹配失败。如果是BF算法，模式串T将会从头并从位置2进行比对。我们通过人脑的思考，模式串这时候应该头对着3，S串的4和T1进行比对才为最优，即T2位置之前的暴力计算都可以省略。最后到T3配对成功。
通过观察可以看出，当比对过程中发生不匹配的时候，不匹配的位置之前的子串如果有首尾呼应的属性的话，就可以实现减少回溯。
这里的首尾呼应即串存在最大（不包括自己）的公共前缀串和后缀串。并且，这是模式串的属性，自然只和模式串有关。
为了描述模式串这个属性，需要引进一个NEXT数组，该数组存贮这当前位置之前子串的最大公共前后缀的长度（即位置）。
当发生匹配不成功的时候，主串S串不再进行回溯，模式串会根据NEXT数组进行相应的回溯。
[TIPS] 我们可以换一种角度思考，以abcab串为例，当发生不匹配的时候，说明前面的是匹配的，前后缀串和中间串这种情况也是一一对应的，如果继续匹配下去前缀串和中间串必定不会匹配成功，也必然是浪费时间的过程，这样一想是不是好理解些了。另外，如有交叉串（如ababab）也是也只是省略了中间串，性质还是一样的。
NEXT数组
NEXT数组是匹配到相应位置时应该回溯的位置（长度），这个回溯的位置和它之前的子串有关。这也导致NEXT数组中存放的都向后偏移一位。
以abab为例，当匹配到第二个b时发生了不匹配，这时说明前面的aba是匹配的，回溯的位置当然是第一个a的位置后面的一个，即回溯到1，这样才能和当前与b比对的进行吻合。这里强调的是NEXT数组里面放的是子串信息。
另外，匹配的时候我们只需要进位比较下一个就行了。如果不匹配的话有两种情况：
1、S串的某位和T串的首位进行比较；
2、S串的某位与T串的非首位进行比较；
面对第一种情况，S串进位，T不变；面对第二种情况，需要参考NEXT数组进行进一步的比对。例如图*2中的T2状态，进一步匹配位置4后，发现还是不匹配，需要继续跟进前面的子串，一直到T串的首尾。
可以看出来，这个数组存放的数据是，首尾是一个标志位可以用※来代替，当匹配到这一位的时候，会进行相应操作。剩下的便是子串的最大前后缀了。所以，abab的NEXT数组是 [※，0，0，1]。一般，为了方便操作和代码简洁※用-1表示。
KMP代码解析
KMP算法主要分为两部分完成：
- NEXT数组的获取
- 使用NEXT数组进行回溯查找
NEXT数组的获取
当提供一个串T，求出他的NEXT数组。我们从递推的角度看(引进长当前长度len、索引i参数)：
当第i个元素和第len个元素进行匹配，匹配成功，NEXT[i+1] = len+1;
当第i个元素和第len个元素匹配失败，但是注意，这时候i前面的len个元素和i前面的len的前面的len个元素是相匹配的。这时候需要考虑着len个元素是否是首尾呼应的。这里举个例子便好理解，串ababcababa，当我们匹配到最后一个a的时候，发现a和c位置匹配不成功，这时候abab是相互匹配的，它的前后缀串是ab，所以比较ab后面的这个元素是否和最后一位的a相同，这时已经递推给子串了，len = NEXT[len]。经过匹配，发现相同，这个时候需要将NEXT[i+1] = len+1。如果一直不相同，则会一直递推到len = -1，然后等于0。
void getKMPNext(char T[]) {
//l是前缀相同的长度
int l = -1, i = 0;
next[0] = -1;
int TL = (int)strlen(T);
while (i < TL) {
if (l == -1 || T[i] == T[l]) {
l++;
i++;
next[i] = l;
} else {
l = next[l];
}
}
}
使用NEXT数组进行回溯查找
在讲NEXT数组的时候，这边的逻辑就已经比较清晰了。设i、j分别是S、T串的索引，并同时从0开始。当索引下的元素值相等，i++、j++；当不相等，将前面最大子串最大前缀的长度获取进行下一步的比对，j=NEXT[i];
int KMPMatchingFunc(char S[], char T[]) {
getKMPNext(T); //将KMP数组初始化一下
int i = 0, j = 0;
//得到两个串的长度。
int SL = (int)strlen(S);
int TL = (int)strlen(T);
while (i < SL && j < TL) {
if (j == -1 || S[i] == T[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j >= TL) {
return i-j;
} else {
return 999;
}
}
算法的优化
KMP和BF算法都可以作进一步的优化。当在一直没有发生匹配的时候,这两种算法都将i、j都以串的长度M、N次进行完了才结束的，根据实际情况是没有必要的。当模式串T的首尾已经和M-N+1进行对齐的时候，剩下的就没必要在比较了。因为，剩下的长度已经不足以支撑该模式串T的匹配成功。
int KMPMatchingFunc(char S[], char T[]) {
getKMPNext(T); //将KMP数组初始化一下
int i = 0, j = 0;
//得到两个串的长度。
int SL = (int)strlen(S);
int TL = (int)strlen(T);
while (i < SL && j < TL) {
if (j == -1 || S[i] == T[j]) {
i++;
j++;
} else {
//优化
if ( i - j + 1 + TL > SL ) {
return 999;
}
j = next[j];
}
}
return i-j;
}
小结
KMP算法通过计算模式串的NEXT数组需要N个数量级的时间复杂度，通过模式串进行匹配需要M个时间复杂度。所以，KMP算法的时间复杂度是O(M+N)。
个人认为，对于绝大多数情况，加法的时间复杂度还是优于乘法的。但是，具体问题具体分析，如果有些业务本身的模式串规律性不强，使用KMP也显得有点复杂。对于有些较长的模式串、并且基础元素不是特别繁多，那么里面的规律相对较多，KMP绝对是不二选择。
欢迎指出错误，学习，交流，提意见！！一起进步、学习~~
