考研复习过程中，看到王道的《数据结构》中对KMP的解释有感而发。感觉王道解释的有点复杂，然后自己理解了一下，在此写一点心得
如果我记得没错，next数组的获得的代码是长这个样子的。
void getNext(char *s, int *next) {
next[1] = 0;
int i = 1;
int j = 0;
while (i < s[0]) {
if (j == 0 || s[i] == s[j]) {
++j; ++i; next[i] = j;
} else
j = next[j];
}
}
接下来把王道《数据结构》中的解释放出来
大家可以尝试着理解一下，如果觉得这么解释更容易理解就可以不往下看了..
接下来就是我对next数组产生从不同角度的理解
先随便写一个字符串：abcc acab cc
根据专科班应有的素质，应该能得出next数组内容为0111 1212 34
步骤为：
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 |
next[0]不存在，next[1]必定等于0（规定的）
如何求得next[3]？
若按照王道《数据结构》中的步骤，很难操作，并且与代码所呈现的逻辑不符，反正我理解起来很别扭。
但仔细看代码，其实很容易就发现next[3]的值就是若next[2]==next[1]则next[3] = next[2] + 1。否则，就和string[1]的next值即next[1]值索引的string字符做比较。
此时
next[1] = 0，而规则就是若比到next值出现0时，直接得出下一个next值为1，或者说同时令index和next[index]加1（next是根据当前所在的值，此时next = 0）
于是就得出next[3]=1。
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 | 1 |
接下来同样让string[3]与string[next[3]]（即string[1]）相比，不等，next为0，加一。。。
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 | 1 | 1 |
同理，注意next[5]的1是根据string[4]与string[next[4]]（即string[1]）相比较得出的
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 | 1 | 1 | 1 |
然后string[5]与string[next[5]]（即string[1]）相比，相等，于是index++，next[index]=next[index-1]+1 （就是加了一）
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 | 1 | 1 | 1 | 2 |
然后理所应当的string[6]与string[next[6]]（即string[2]）相比，不一样，转而string[6]与string[next[next[6]]]（即string[1]），又不同，而此时next [next[next[6]]] == 0，于是next[++index] = next[next[next[6]]] + 1
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 | 1 | 1 | 1 | 2 | 1 |
。。。
。。。
。。。
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 | 1 | 1 | 1 | 2 | 1 | 2 | 3 | 4 |
