1、字符串匹配——KMP算法
当我们想要想要在一个字符串中找到一个子串，如在字符串"aaabaaacaaad"中查找是否存在模式串"aaad"。首先常规的算法如下：
1、先比较字符串 与 模式串 第一个是否相等，相等则匹配下一个
2、比较第二个字符是否相等，相等则匹配下一个
3、比较第三个字符是否相等，相等则匹配下一个
4、比较第四个字符是否相等，这时发现不相等
5、开始重新匹配，依次再和字符串的下一个字符相比较
可以看到当我们第一次匹配了前三个aaa相等时，而在第四位不等时，前面四个就根本不用再反复比较了，因为在模式串中根本没有b这个字符（模式串就是下面的 aaad）
所以当我们比较完上面这个后，应该直接进行下面的比较
可是上面的这种方式，我们可以一眼就看出来有哪些是不必要的比较，程序又该如何描述呢？又或者说，当匹配不成功时，究竟下一个要比较的字符是谁，我们如何知道？
KMP算法解决了这个问题，将字符匹配算法优化到了极致
KMP算法，全称Knuth-Morris-Pratt算法，由这个三个作者共同创作 Donald Knuth、James H. Morris、Vaughan Pratt。
其核心在于next数组，就是在模式串中，寻找最大相同前后缀，并在字符比较时遇到错误的匹配，主字符串不用回溯到最初的位置+1，只需要停留在原位，而模式串则根据next数组确定要移动的位置。
我们来详细解释上面的话。
1、在模式串中，寻找最大相同前后缀。
现在我们要在字符串 “abcab??????”(注意： ？ 代表暂时不知道为什么字符) 中查找是否有模式串 “abcabd”。
第一步，比较 字符串第一个字符 与 模式串第一个字符 是否相等。
发现相等， 继续向后检查
我们一直向下检查到了b字符，还是相等，继续检查最后一个字符。我们用大致这样方式判断，
if(字符串[i] == 模式串[i])
这时发现不相等，下一步我们是否该让模式串再重头开始，用a和字符串b相比较，其实这是没意义的。我们可以发现，当我们比较d和 ？发现不相等时，其实 字符串前面5个字符 和 模式串前面的 5个字符 一定是相等的，可是怎么利用这个信息呢？
现在我们假设按照之前的做法，当重新开始匹配时，想要比较 ？== 模式串[i],
则先要将前面的四个字符（ b 、c、a、b）重新再匹配一遍，直到都匹配成功。而这里很明显会匹配失败，所以我们右移。
这个也匹配失败，继续右移
这个时候，发现已经匹配成功了，可以比较 ？== 模式串[i] 了。我们发现当匹配失败时，字符串不断的重新匹配前面的字符，只是为了之后可以比较新的字符（？== 模式串[i] ）。而这一步则是判断 字符串的尾部 与 模式串的头部是否相等。如果前面可以预知其相等，则可以跳过前端的反复比较，直接比较 ？== 模式串[i] 。
通过上面的一步一步进行，可以发现当出现匹配失败时，我们其实就是在寻找 其匹配成功的内容中相同的首尾部。
如 当 字符串 ？ != 模式串[i] ， 我们开始用 字符串 ？前面字符的后缀 与 模式串前面字符的前缀 比较 。
字符串 bcab == 模式串 abca。 不等则各-1.
字符串 cab == 模式串 abc。 不等则各-1.
字符串 ab == 模式串 ab。 相等，开始匹配 ？
这就是所谓的最大相同前后缀。这里还不对，再看下面。
2、主字符串不用回溯到最初的位置+1，只需要停留在原位
当我们匹配失败时，我们开始找已经匹配过的字符串最大后缀 与 模式串最大前缀 ，这样就因为知道其前后缀相等，则不需要再一一比较，从而直接开始从 ？ 比较，则字符串就不需要向前回溯了。
因为匹配过的说明这部分的字符串与模式串是相等的。也就是说在已经匹配过的部分中，字符串 = 模式串。而比较字符串最大后缀 与 模式串最大前缀，其实就是比较 模式串最大后缀 与 模式串最大前缀。
原本是想找出它们相等
可是由于它们是相等的
现在变成了找出它们相等
这才是最大相同前后缀。这样有一个很大的好处，就是我们的最大前后缀只通过模式串就可以完成，所以我们不需要知道字符串是什么，就可以知道当模式串匹配失败时，其最大前后缀是什么。
我举的这个例子，是当匹配失败时，其最大前后缀为 ab，当其他位置匹配失败时，也同样可以算出来。我们如果一开始就把模式串的每一个位置匹配失败时，都算出其最大相同前后缀。
如：d匹配失败时，其最大前后缀为2，其他的也这样算，并将每一个算出来的值都存入一个数组中，其数组一一对应模式串。这个数组就是next数组。
3、next数组。
既然找出 最大相同前后缀，可以让字符串的指针不用回溯。并且只需要 模式串就可以找出，那我们来看下吧。
等下，这里还要再补充一下最大相同前后缀的作用。其目的是为了在匹配失败时，字符串的指针不用回溯，通过移动模式串来进行重新匹配。
如上面的情况，当 ？与 d 匹配失败时，移动模式串，让 ？与 c 开始匹配。这个时候虽然 ab 为最大相同前后缀，但我们其实是想让最大相同前后缀的后面一个元素与 ？匹配，所以其对应next数组的值 不是 2，而是 3 。这也是为什么叫next数组，因为其中保存的值是下一个要匹配的位置（next的意思为下一个）（可既然是数组，为什么不按照索引来一一对应呢？如c的索引就是2啊。）
为什么不按照索引，看下面这种情况。当第一个字符就配置失败时，其实我们需要移动的是字符串，将其向后移动一格，但为了与其他情况保持一致，我们依旧要移动模式串使其可以再次匹配。
我们在next[0]的位置设置值为 -1，其实设置任何一个特别的值都行，-10/-9999都可以，这只是为了在代码中好判断它，这里还是用-1，当第一个字符匹配失败时，原先的 ？将指向 0，之后将让 i++,j++。使字符串指针与模式串指针向后移动一格，匹配新字符。
计算next数组 ：（匹配的字符不能等于自身）
当第一个位置匹配失败时，其中没有匹配成功的串.注意：第一个位置的next值始终都是0，也就没有最大相同前后缀。
最大相同前后缀： 0
其next数组对应的值为：0
next数组此时为： [ -1 , 0 ]
当第二个位置匹配失败时，其中有一个匹配成功的字符,但它是和自身比较的，不算。注意：第二个位置的next值始终都是1（图片的水印占的地方太大了，难受）
最大相同前后缀： 0
其next数组对应的值为：1
next数组此时为： [ -1 , 0 , 1 ]
当第三个位置匹配失败时，其中有二个匹配成功的字符，有0相同前后缀。
最大相同前后缀： 0
其next数组对应的值为：1
next数组此时为： [ -1 , 0 , 1 , 1 ]
当第四个位置匹配失败时，其中有3个匹配成功的字符，有0个相同前后缀。
最大相同前后缀： 0
其next数组对应的值为：1
next数组此时为： [ -1 , 0 , 1 , 1 , 1]
当第5个位置匹配失败时，其中有四个匹配成功的字符，有 1 个相同前后缀。
最大相同前后缀： 1
其next数组对应的值为：2
next数组此时为： [ -1 , 0 , 1 , 1 , 1 , 2 ]
当第6个位置匹配失败时，其中有五个匹配成功的字符，有 3 个相同前后缀。
第一个相同前后缀 = 1 （a）
第二个相同前后缀 = 1 (b)
第三个相同前后缀 = 2 (ab)
最大相同前后缀： 2
其next数组对应的值为：3
next数组此时为： [ -1 , 0 , 1 , 1 , 1 , 2 , 3]
4、模式串则根据next数组确定要移动的位置。
现在我们已经得到了 next 数组，注意当我们在创建next数组时，只用到了模式串，而此时这个next数组，在和任何字符串匹配时都同样有效。
下面是模式串与next数组的情况。
再说一下next数组的作用，当某一个位置匹配失败时，不用移动字符串指针，只需要找到模式串的next数组，并按照失败位置的next值，将其值赋值给 模式串指针 j ，将模式串移动到 next[ j ] 即可。
当第一个位置匹配失败时
令 模式串指针 j = 0
匹配 模式串的 next[ j ] 的位置， 位置为 a 前面的字符，-1，在代码层面会做处理，暂时先不用管。
当第二个位置匹配失败时
令 模式串指针 j = 1
匹配 模式串的 next[ j ] 的位置， 也就是 a。
当第三个位置匹配失败时
令 模式串指针 j = 1
匹配 模式串的 next[ j ] 的位置， 也就是 a。
当第四个位置匹配失败时
令 模式串指针 j = 1
匹配 模式串的 next[ j ] 的位置， 也就是 a。
当第五个位置匹配失败时
令 模式串指针 j = 2
匹配 模式串的 next[ j ] 的位置， 也就是 b。（其实next数组也有不足之处，这里匹配b已经失败了，结果重新匹配的位置又是 b ，肯定还会匹配失败。别急，那是下一章要讲的 nextval 数组。先学懂 这章吧 ！）
当第六个位置匹配失败时
令 模式串指针 j = 3
匹配 模式串的 next[ j ] 的位置， 也就是 c。
好了，说了这么多了，下面开始上代码。
5、C语言代码
/**
* T 为 模式串, char *T 为字符数组指针，
* const：表示不能修改字符串的值（但可以修改指针指向地址）。
* next[] ： 为 整数数组，用于存储匹配表
* length： 模式串的长度
*/
void get_next(const char *T, int next[], int length) {
int i = 0, j = -1;
next[0] = -1;
// i < length，这里用 < 而不是 <=，是因为如果 = length，则字符就匹配成功了，
while (i < length) {
if (j == -1 || T[i] == T[j]) {
i++;
j++;
next[i] = j;
} else {
// 回溯，i 不变，让j-1.
j = next[j];
}
}
}
//kmp
int get_index_kmp(const char *S, const char *T) {
int i = 1, j = 1;
int sLength = strlen(T);
int tLength = strlen(T);
int next[tLength + 1];
get_next(T, next, tLength);
while (i <= sLength && j <= tLength) {
if (i == 0 || S[i] == T[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j > tLength) {
return i - tLength; // 匹配成功
}
return 0;
}