KMP算法详解
一、什么是KMP算法
KMP是一种字符串匹配算法。比如，一个字符串ASDFASDFASD，我想知道其是否包含ASDFS这个子串，这个时候就用到了KMP算法啦。这时候可能有人就要问啦，不就是字符串匹配嘛，这有啥难的，逐个字符比较就完事了，兄弟，咱要考虑效率啊，KMP算法相比于暴力匹配则拥有有更好的执行效率。接下来我们来学习它的实现思路。
二、KMP字符串匹配过程推演
为了方便大家理解，我们先通过一系列图片，演示下KMP的比较过程：
假设我们有一个字符串AD ASDFSD ASDFABBAA，我们需要校验其是否包含ASDFA这个子串：
1）首先比较字符串与子串首个字符，此时是不相同的，于是子串后移一位。
2）由于D与A不同，则子串仍要后移一位。
3）就这样不断比较，直到出现字符串与子串首字符相同。
4）此时比较字符串与子串的下一个字符，是相等的则继续比较。
5）直到遇到不同的字符，这时候KMP的优势就会体现出来：
如果是暴力匹配，此时肯定是要将子串向后移动一位，继续比较，但是这样做效率真的太低了，我们通过前面几轮的比较已经知道ASDF是相同的，那能否根据已知信息不再比较这些字符呢？这里就需要引入【部分匹配表】，如下所示：
| 子串 | A | S | D | F | A |
| 部分匹配值 | 0 | 0 | 0 | 0 | 1 |
这张表是KMP算法的核心，关于这张表如何计算后面会讲解，大家先继续往下看。
6）此时我们知道S与A不匹配，然后前面四个字符都是匹配的，最后一个匹配字符F的匹配值是0，我们通过如下公式计算子串移动位数：4 - 0 = 4。
移动位数 = 已匹配的字符数 - 对应的部分匹配值
7）移动后仍然重复前面的流程逐个字符比较，最终找到匹配的子串：
我们可以看到KMP可以减少比较次数从而提高计算效率，那么这个算法最核心的【部分匹配表】是如何得到的呢？
三、部分匹配表
首先需要介绍下前缀、后缀及部分匹配值，这三个名词的概念：
前缀：指除了最后一个字符以外，一个字符串的全部头部组合；
后缀：指除了第一个字符以外，一个字符串的全部尾部组合
部分匹配值：就是前缀和后缀的最长的共有元素的长度。
我们以ASDFA为例进行说明：
| 子串 | 前缀 | 后缀 | 部分匹配值 |
| A | [] | [] | 0 |
| AS | [A] | [S] | 0 |
| ASD | [A, AS] | [D, SD] | 0 |
| ASDF | [A, AS, ASD] | [F, DF, SDF] | 0 |
| ASDFA | [A, AS, ASD, ASDF] | [A, FA, DFA, SDFA] | 1 |
因此，我们可以明白KMP的实现思路就是：当一次匹配过程中在模式串j位置处出现字符不等时，不需要回溯主串上面的指针 i，而是利用模式串P在 j-1位置的部分匹配值k将模式向右滑 j-k个字符，然后继续进行比较。
四、代码编写
最后我们以Java为例，编写KMP算法的代码：
public class KMPDemo {private int[] next;private void initNext(String pattern) {int i = 0;int j = -1;int len = pattern.length();next = new int[pattern.length()];next[0] = -1;while(i < len - 1) {if (j == -1 || pattern.charAt(j) == pattern.charAt(i)) {i++;j++;next[i] = j;} else {j = next[j];}}}public int search(String s, String pattern) {int i = 0;int j = 0;int sLen = s.length();int pLen = pattern.length();initNext(pattern);while(i < sLen && j < pLen) {if (s.charAt(i) == pattern.charAt(j)) {i++;j++;} else {if (next[j] == -1) {i++;j = 0;} else {j = next[j];}}if (j == pLen) {return i - j;}}return -1;}public static void main(String[] args) {String s = "AD ASDFSD ASDFABBAA";String pattern = "ASDFA";KMPDemo kmp = new KMPDemo();System.out.println(kmp.search(s, pattern));}