0.说明
由于大部分文章直接从算法入手，即使配合丰富的动图，理解起来也有一些难度。在自己理解和实现后，用推导的思路聊一聊KMP。
当进行子字符串查找时，最简单的方法是尝试将母字符串的每一位依次看作首位，和目标字符串进行逐字符对比。这样非常易懂，但效率偏低。
如果母字符串长度为m，目标字符串长度为n，算法时间复杂度可能达到m*n。在基因工程等（字符集较少，相对容易大段重复，且目标串和母串都非常长）特殊情况下这样的时间复杂度是较难接受的。这时非常需要思考如何进行优化。
1.寻找可跳过的场景
相对容易想到（其实也很难）的一个方向是跳过一些无需重复的检查的场景，那我们先找一找有哪些场景可以跳过。
当我们有
母串：abceabcfabcegff
目标：abcfabck
开始，进行逐字符比较，从
v
abcfabcfabcegff
abcfabck
^对比至
场景1:
v
abcfabcfabcegff
abcfabck
^发现不一致了。按最简单的做法，我们需要改变首字符位置重新匹配，如下
v
abcfabcfabcegff
abcfabck
^周而复始，可以发现迟早我们将对比至
场景2
v
abcfabcfabcegff
abcfabck
^而这个场景和当初场景1时的
v
abcfabcfabcegff
abcfabck
^ 是多么的相似啊（都将需要对比abc，且都能匹配上）。如果我们能跳过刚才这里已经对比过的abc。如果能避免重复对比，直接进行
v
abcfabcfabcegff
abcfabck
^ 至少能省下对比abc的时间。嗯，虽然看起来优化价值不大，如果能很低成本做，到至少还是稍有价值的（省了三次对比）。
但怎么跳呢?容易想到的是在第一次对比后
0000300v
abcfabcfabcegff
abcfabck
^我们为a记录一个数字3，等于abc的长度，这样就可以当第二次对比至这个a时
场景2
00003
v
abcfabcfabcegff
abcfabck
^直接根据其记录的数字3，将对比指针跳转至后方第3位。
场景2
0000300v
abcfabcfabcegff
abcfabck
^这样就省略了abc的重复对比。
2.前串首尾最大重合长度
我们可以对比两个场景，观察一下这个abc是哪来的
场景1:
v
abcfabcfabcegff
abcfabck
^
场景2
v
abcfabcfabcegff
abcfabck
^可见一个来自于目标串k字符前部的尾部，另一个来自于目标串的首部。
如果我们有低成本的方式（先别被能否实现所束缚，用优秀产品经理的思维去构思产品应用场景），去知道目标串的每个字符的前面，有多长的首尾重复（如对于abcfabck，其中的k而言，应是abc长度为3的重复）。
对于abcfabck整串而言，每个字符对应的前串首尾重合长度可以是
a b c f a b c k
0 0 0 0 0 1 0 3我们就可以每次字符比较后，为母串添加向后的跳转标记，如在对比至
v
abcfabcfabcegff
abcfabck
^代表我们已经成功匹配了b前方的a，而这个a是可以为未来省略首字母a对比提供指导的，所以可以在母串对应位置根据b的前串首尾重合长度进行标记：
1v
abcfabcfabcegff
abcfabck
^同理，对于目标串中的k也是一样。只是此时我们也是想对母串的a添加跳转指引。那我们到底保留1还是3呢？
容易发现数字越大能跳过的距离越远，省下的对比次数越多，所以自然应该是选择更大的3。
0000300v
abcfabcfabcegff
abcfabck
^也是因此，我们应尽可能为目标串找到最长的前串首尾最大重合长度。
但是，如果我们的目标串是
a a a a a
0 1 2 3 4以最大进行标记会是如上的情况。
实际应用时会标记为
4000v
aaaabeafaaa
aaaaa
^这对即将进行的
4000
v
aaaabeafaaa
aaaaa
^ 没有任何帮助（因为第一个a已经不再被当首位）。因此，我们需要避免标记首位，对应的，我们可以限制“最长”的长度为目标串长度减1。以有效地标记，方便未来跳过：
a a a a a
0 0 1 2 3//最长目标串长度减1
0300v
aaaabeafaaa
aaaaa
^ 3.还有可以跳过的场景吗
目前为止，我们也仅仅是在最简单的对比方式下进行了少量字符对比时的跳过，但依旧需要考虑母串的每一字符作为首字母的情况，复杂度并没有减少多少，而且我们还留下了计算“前串首尾最大重合长度”这么一个坑。
我们可以进一步考虑是否能在遍历母串每个字符作首字符时跳过一些。
继续观察我们上方的母串和目标串。
0000300v
abcfabcfabcegff
abcfabck
^在第一次匹配f和k匹配失败后。我们还尝试了
0v003
abcfabcfabcegff
abcfabck
^ 00v03
abcfabcfabcegff
abcfabck
^ 000v3
abcfabcfabcegff
abcfabck
^ 这三种情况，但这三种尝试是有意义的吗？稍加对比后可以发现并不必要，由于我们已经记录了“前串首尾最大重合长度”并标记至母串的对应字符位置，那没有被标记的字符一定是无法作为首字母被目标串匹配的。
这么说在一次匹配失败后，我们至少是可以跳至最近一个有被标数字的位置。
但此时需要考虑一个特殊情况：没有任何母串字符被标记（0看作没有标记）。
没有任何母串被标记意味着什么？我们可以构造一个例子看看
a b c f c k
0 0 0 0 0 0
v
abcfabcfabcegff
abcfck
^这种情况下由于已匹配的所有字符的“前串首尾最大重合长度”都为0，这种情形下，看似没有能力为未来的跳过提供帮助。
实则提供了很重要一个信息：已匹配的都无法作为首字符和目标串匹配。
所以我们可以跳过所有已匹配的，直接开始尝试当前字符作首字符：
v
abcfabcfabcegff
abcfck
^4.还能不能再省点事
我们已经发现，最开心的情形是“没有任何母串字符被标记”，可以轻松跳过很多。但这毕竟对目标串有一些要求，那不满足这些要求是，是否还有优化空间呢？
我们可以看看母串有多标记时是什么情况:
目标串：
a a a a a a a f a b
0 0 1 2 3 4 5 6 0 1
第一轮：
060000001v
aaaaaaafacaaaaa
aaaaaaafab
^
下一步跳至最近的有标数字的首位，并根据数字进行前移：
0600000v1
aaaaaaafacaaaaa
aaaaaaafab
^甚至可以多构造两组实例进行尝试，可以发现，当有多个标记时，以最近的标记作首位匹配都会失败。
为什么呢？稍思考可以发现，每个标记位置往前便宜其标记的数字，恰是标记时的字符所在的位置（废话，就是这样进行的标记），首位重复长度的最大扩大速度也只和位置挪动一致（最多同时增加1），而一旦有首位重复的断点就将归零。于是乎越晚进行的标记一定匹配地也越多，且目标位置越靠后。
于是一个靠前的标记意味着能匹配比如x个，而一个靠后的标记必然代表x之后会有断点（否则靠后的应该是去更新前一个标记而非标一个新的）。
于是又得到一个重大进步：我们原来可以忽略掉非最后的标记直接跳转。
5.简化实现方式
前面一直在进行分析，但实现方式可能会有很多冗余（比如马上将看到的母串数字标记）。
由于已知多个标记也仅有最后一个有用，而最后一个来自于匹配失败的那次（如果匹配失败时，对应目标字符首位最大重复为0，正好代表前面标记无效，等同于没有标记）。
所以我们并不需要真正对母串进行标记，可以直接根据结果一次性跳转即可。可以省了一个标记数组。
同时我们还可以发现，无论是没有标记还是最后一次有标记，跳转之后母串的对比指针都是刚好没有变化（可以看看之前的例子）。于是可以省一个首字符指针。同时此特征也体现出当前算法下不需要回溯的效率优越性。
最后为了方便高效地实现目标串的偏移，通常选择不动字符串，而移动对比指针的方式（运动是相对的），如将
v
abcfabcfabcegff
abcfck
^中的目标串移动至
v
abcfabcfabcegff
abcfck
^等效于将其对比指针移动至
v
abcfabcfabcegff
abcfck
^6.填前串首尾最大重合长度坑
做完这些准备工作，计算复杂度已经被我们降低至了O(m+n)。计算方式很简单，观察指针的运动就可以感知出来。
但是，计算目标串的“前串首尾最大重合长度”我们还迟迟没有讨论。如果用最傻瓜的方式进行匹配尝试，这一块复杂度就可能达到O(n*n)。
好在我们已经知道了如何快速在母串中查找目标串，我们也可以用近似的思路去快速在目标串中查找首尾重复串。只是这次是自己和自己对比。
首先前两个字符的值肯定为0，于是可以直接赋值。
现在考虑第三个字符，需要关心第一个和第二个是否一致，比如：
v
aabaaabc aabaaabc
aabaaabc 00
^ 如果一致，则置其值为1，并且前进目标串的指针（代表前面的匹配成功），再前进母串的指针（代表我们要计算下一个了，并且也可以在移动至后看到确实也需要这样对比重复的子串）：
v
aabaaabc aabaaabc
aabaaabc 001
^ 发现不匹配，则需要将目标串平移，该平移多少呢？仔细看看可以发现当前的处境和我们去用任意目标串匹配任意母串没有任何区别：需要平移至目标位置减最长首尾重复长度。
对应着指针需要平移至最长重复长度值所对应的目标串数组位置，例子来看是0，即
v
aabaaabc aabaaabc
aabaaabc 001
^ 接着再进行匹配。这时发现还是无法匹配，但由于位置已经是零，再往零移动只会死循环。同时我们观察也能发现确实也没有重复首尾串存在，所以可以放心地将长度置0，并且前进母串指针准备下一个计算：
v
aabaaabc aabaaabc
aabaaabc 0010
^ 就这样，我们可以在O(2n)的时间复杂度下，计算出整个目标串的前部最长首尾重复长度。
7.C语言实现
有了思路过后，实现反而是小事。这里用C语言进行实现。
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
void set_eq_len(char *b,int *eq_len)//计算目标串b的每个字符对应的前部最长首尾重复长度
{
int i = 1;
int j = 0;
eq_len[0] = 0;
eq_len[1] = 0;
while(i < strlen(b) - 1)
{
if(b[i] == b[j])
{
i++;
j++;
eq_len[i] = j;
continue;
}
if(j == 0)
{
i++;
eq_len[i] = 0;
}
else
{
j = eq_len[j];
}
}
}
int kmp(char *a,char *b)//a为母串，b为目标串
{
int *eq_len = calloc(strlen(b),sizeof(int));
set_eq_len(b,eq_len);
//打印前部最长首尾重复长度
for(int i = 0;i < strlen(b) ;i++)
{
printf("%c\t",b[i]);
}
printf("\n");
for(int i = 0;i < strlen(b) ;i++)
{
printf("%d\t",eq_len[i]);
}
printf("\n");
//开始匹配母串
int i = 0;//母串匹配指针
int j = 0;//目标串匹配指针
while(i < strlen(a))
{
if(a[i] == b[j])
{
if(j == strlen(b) - 1)//success
{
return i - j;
}
i++;
j++;
continue;
}
if(j == 0)
{
i++;
continue;
}
j = eq_len[j];
}
return -1;
}
int main()
{
printf("kmp:%d",kmp("asdffaaaaabacabaeqwe","aaaaaac"));
return 0;
}
8.参考资料
https://www.zhihu.com/question/21923021
https://wiki.jikexueyuan.com/project/kmp-algorithm/define.html