对于第2个字符a，其前面有2个字符ab，不存在与b或ab相等的字符，因此根据情况3，next[2] = 0；对于第3个字符a，其前面有3个字符aba，最长只有字符（第0个）和第2个字符a（紧跟第3个字符）相等，因此根据情况1，next[3] = 1；
对于第4个字符b，其前面有4个字符abaa，最长只有字符（第0、2个）和第3个字符a（紧跟第4个字符）相等，因此根据情况1，next[4] = 1；
对于第5个字符c，其前面有5个字符abaab，最长有子串ab（第0、第1个字符的组合）和第3、第4个字符的组合ab（紧跟第5个字符）相等，因此根据情况1，next[5] = 2；
对于第6个字符a，其前面有6个字符abaabc，没有子串与含有c（紧跟第6个字符）的字串相等，因此根据情况3，next[6] = 0；
对于第7个字符c，其前面有7个字符abaabca，最长只有字符与第6个字符a（紧跟着第7个字符）相等，因此根据情况1，next[7] = 1；
只要子串不是很长，可以一眼求出next数组中各元素的值。
下面看如何用程序来求next数组的值。
如果已有next[j] = k（假设k为已知），这说明在子串的前j个字符中，存在前面推论出来的关系式：
P0 P1 ... Pk-1 = Pj-k Pj-k+1 ... Pj-1
下面我们继续求next[j+1]，这就要分两种情况开看：
1、若Pk = Pj，则表明在子串中，有如下关系式：
P0 P1 ... Pk != Pj-k Pj-k+1 ... Pj
那么就有next[j+1] = k+1,即next[j+1] = next[j] + 1.
2、若Pk != Pj，则表明在子串中，
P0 P1 ... Pk != Pj-k Pj-k+1 ... Pj
此时，我们同样可以将其看做是一个模式匹配的过程（子串与主串均为Ptn），由于Pk != Pj，首次出现不匹配，那么应该取子串的第next[k]个字符与主串的第j个字符再做比较。
我们假设next[k] = t，重复上面的比较，如果Pt = Pj，则next[j+1] = t + 1 = next[k] + 1，而如果Pt != Pj，则继续讲子串向右滑动，取其第next[t]个字符与子串的第j个字符再做比较，直到Pj和子串中的某个字符匹配成功，此时next[j+1]即为求得的值，或不存满足上述等式的k，此时next[j+1] = 0.
同样以如下字符串为例进行计算：
abaabcac
对于第1个字符b，由于其前面的字符串a中不存在满足上面等式的k，因此根据情况3，next[1] = 0；对于第2个字符a，由于其前面的字符串ab中不存在满足上面等式的k，因此根据情况3，next[2] = 0；
对于第3个字符a，其前面的字符串为aba，由于P0=P2，因此next[3] = 1；对于第4个字符b，其前面的字符串为abaa，由于next[3]=1，而P3!=P1，则需要比较P3和P0（next[1]=0），而P3=P0，因此next[3] = next[1]+1 = 1；对于第5个字符c，其前面的字符串为abaab，由于next[4]=1，而P4=P1，因此next[5] = next[4]+1 = 2；对于第6个字符a，其前面的字符串为abaabc，由于next[5]=2，而P5!=P2，则需要比较P5和P0（next[2]=0），由于P5!=P0，因此不存在任何k值满足上面的等式，next[6]=0；
对于第7个字符c，其前面的字符串为abaabc，由于next[6]=0，且P6=P0，因此next[7] = next[6]+1 = 1；
依照KMP算法，我们可以得到求next数组的算法，代码如下：
/*
求next数组中各元素的值，保存在长为len的next数组中
*/
void get_next(const string &Ptn,int *next,int len)
{
int j = 0;
int k = -1;
next[0] = -1;
while(j
我们在程序中加入输出next数组的代码，测试KMP算法，得到的结果如下：
前缀数组next的改进
上面定义的next数组在某些情况下是可以继续改进的。考虑如下两个字符串：
主串：aaabaaaab
子串：aaaab
通过手算，我们可以看出子串的next数组的各元素为：-1、0、1、2、3。当主串和子串在第3个字符处出现不匹配时，即Tag[3]!=Ptn[3]，则由next[3]=2，因此需要比较Tag[3]和Ptn[2]，再根据next[2]=1，接下来需要继续比较Tag[3]和Ptn[1]，再比较Tag[3]和Ptn[0]。而实际上，由于子串中的Ptn[0]、Ptn[1]和Ptn[2]这3个字符和主串中的Tag[3]相等，因此不需要再一一进行比较，可以直接进行Tag[4]和Ptn[0]的比较。
针对普遍情况而言，若next[j] = k,且子串中Ptn[j] = Ptn[k]，则当Tag[i]!=Ptn[j]时，不需要再将Tag[i]和Ptn[k]进行比较，而可以直接和Ptn[next[k]]进行比较，也即是，next[j]=next[k]，而不是next[j]+1。因此上面求next数组的代码可以修改如下：
/*
求next数组的改进数组中各元素的值，保存在长为len的nextval数组中
*/
void get_nextval(const string &Ptn,int *nextval,int len)
{
int j = 0;
int k = -1;
nextval[0] = -1;
while(j
这样，子串aaaab的nextval数组的各元素为：-1、-1、-1、-1、3。