next数组的值其实就是【当前位置之前的字符串】的最长公共子缀长度
————————————————————————————
举个例子：
父串ABAABACA
当我们在计算C字符对应的next数组值时，我们其实就是要计算ABAABA这个字符串的最长公共子缀。
ABAABA的前缀有A、AB、ABA、ABAA、ABAAB
                  后缀有A、BA、ABA、AABA、BAABA
最长的公共子缀是ABA，长度为3，所以C这个位置的next数组值就是3。
由于第一个字符之前没有任何字符，所以我们规定第一个字符处的next数组值为-1；第二个字符之前只有1个字符，但是我们规定子缀是不能包含父串本身的，所以最长公共子缀为0；其他位置的按照标准计算即可。
根据定义，父串ABAABACA的next数组值为：

KMP算法解决的问题是在父串中查找子串是否存在。
————————————————————————————
我们举例来说明KMP的工作过程
父串txt=BBCABCDABEABCDABCDABDE
子串str=ABCDABD
（1）求出子串str的next数组

所以KMP的基本工作原理就是：

1. 若子串、父串相等，则同时往后移动
2. 若子串、父串不等，则子串移动到next[i]这个位置
3. 若i=-1时子串、父串同时往后移动

next数组的原理上面已经讲了，现在说说怎么写next数组的求解代码。
首先能想到的一个暴力方法是，每一位在求解时，都把它之前的子串的前后子缀由长到短逐渐比较。
————————————————————————————
比如AAABBADA，我们在求解D所对应的next数组值时，将前面的子串AAABBA提出来：

1. 先比较AAABB和AABBA
2. 不等，则比较AAAB和ABBA
3. 不等，则比较AAA和BBA
4. 不等，则比较AA和BA
5. 不等，则比较A和A
6. 发现等，所以next数组值是1

写成代码就是：

有了求next数组的代码，KMP的代码就简单多了，我们直接按照上面的标准来写：
所以KMP的基本工作原理就是：

1. 若子串、父串相等，则同时往后移动
2. 若子串、父串不等，则子串移动到next[i]这个位置
3. 若i=-1时子串、父串同时往后移动