KMP算法做的事情就是用来进行字符串匹配，并且尽量高效地去移动模式串，避免不必要的匹配。
在字符串A中找寻是否存在部分等于字符串B，在这里我们把B看做模式串，去跟字符串A做匹配
这个匹配的规则是这样的，对于模式串B的某一位出现了失配的情况，那么如果前面存在最长k位的部分匹配，就将模式串向后移到让模式串的k+1位对着主串当前位；如果前面不存在部分匹配，那么不好意思，只能从头开始重新匹配。
以模式串ADABCADADA为例：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| A | D | A | B | C | A | D | A | D | A |
在第1位的A失配的时候，由于A前面并没有模式串的部分和主串匹配，所以在主串的下一位还将和模式串的第1位A进行匹配，也就是说在当前第1位A处的主串和第0位（第1位的A之前的部分）去匹配；
在第2位的D失配的时候，由于D前面并没有模式串的部分和主串匹配，所以在主串的这一位将和模式串的第1位A重新开始匹配；
在第3位的A失配的时候，由于A前面并没有模式串的部分和主串匹配，所以在主串的这一位将和模式串的第1位A重新开始匹配；
在第4位的B失配的时候，发现B前面存在第3位的A和模式串开头的A匹配，并且这是匹配的最大距离了，所以在下一次匹配的时候，第1位的A将移到现在第3位的A这个位置，那么现在的第4位就变成了模式串的第2位；
在第5位的C失配的时候，由于C前面并没有模式串的部分和主串匹配，所以在主串的这一位将和模式串的第1位A重新开始匹配；
第6位同理第3位，当该位置失配时，和模式串第1位匹配；
第7位同理第4位，当该位置失配时，和模式串第2位匹配 ；
在第8位的A失配的时候，发现A前面存在第6位的A和模式串开头的A匹配，第7位的D和第2位的D匹配，并且这是匹配的最大距离，所以在下一次匹配的时候，第1位的A将移到现在第6位的位置，那么现在的第8位将变成原来的第3位；
第9位同理第8位，当该位置失配时，和模式串第4位匹配；
第10位同理第8位，当该位置失配时，和模式串第3位匹配；
那么，当前模式串的next数组就是：0 1 1 2 1 1 2 3 4 3
书上有个求next数组的公式：
简单的说：
模式串第一位的next[1]=0；
如果在第j位前面存在部分匹配长度为m，那么next[j]=m+1；
不是前面两种情况的话那么next[j]=1。
反复思考了好久才理解了，希望可以帮助到大家。