为了让同学们能够速成KMP这里直接放出具体的求解办法

step1:求解原字符串的前缀后缀最长公共元素长度

首先说啥是前缀后缀公共元素：

对于字符串P=p0 p1 ...pj-1 pj ,如果存在(p0 p1 ...pk-1 pk) = (pj- k pj-k+1...pj-1,pj)，

那么就说明P中有最大长度为 k + 1 的相同前缀后缀。

什么意思呢 ？ 举个例子，比如字符串"abcab"，要找的是它的前缀和它的后缀相同的部分，也就是“ab”。

然后对于整个字符串，我们可以求出来它的各个子串的前缀后缀的公共元素的最大长度，并且列出如下的表：

a b c a b
0 0 0 1 2

step2:右移得到next数组

步骤就是将上方得到的表同时向右移一个位置,在第一个位置补上 - 1 即可
串     a b c a b
next  -1 0 0 0 1

step3:检查更新 nextval 数组

nextval数组的求解是基于next数组的,其中一个特征就是 next和nextval数组的第0位永远都是 -1

得到next数组后，从左至右进行检查，设next[j]=k，
若k >= 0 且 p[j] == p[k]，则令nextval[j] = nextval[k]，否则nextval[j] = next[j]。
这个看起来可能有点抽象,所以我们不妨来模拟一下


那么第一个就从nextval[1]开始

要求解nextval[1]那么我们看到next[1] = 0,那么串p[0] = a 而p[1] = b,

显然二者不相等,因此nextval[1] = next[1] = 0;


同理可得 
p[0] != p[2] 那么nextval[2] = 0,
p[0] == p[3] 那么nextval[3] = nextval[0] = -1,
p[1]==p[4] 那么nextval[4] = nextval[1] = 0,
由此我们就可以得到下列表 

串           a  b  c  a  b
next        -1  0  0  0  1
nextval     -1  0  0 -1  0



同理我们再举个例子加深一下印象

设串为:abcabaa

按照相同的步骤
1.我们要求解原字符串的前缀后缀最长公共元素长度

a b c a b a a
0 0 0 1 2 1 1

2.右移得到next数组

next -1 0 0 0 1 2 1

3. 检查更新 nextval 数组
串:         a   b   c   a   b  a  a
next       -1   0   0   0   1  2  1

nextval[0] = -1;
p[1] = b,p[next[1]] = a,二者不相同直接抄下来,因此nextval[1] = 0;
p[2] = c,p[next[2]] = a,二者不相同直接抄下来,因此nextval[2] = 0;
p[3] = a,p[next[3]] = a,二者相同,因此nextval[3] = nextval[next[3]] = -1;
p[4] = b,p[next[4]] = b,二者相同,因此nextval[4] = nextval[next[4]] =  0;
p[5] = a,p[next[5]] = c,二者不相同直接抄下来,因此nextval[5] = 2;
p[6] = a.p[next[6]] = b,二者不相同直接抄下来,因此nextval[5] = 1;

因此
串:         a   b   c   a   b  a  a
next       -1   0   0   0   1  2  1
nextval    -1   0   0  -1   0  2  1


因此我把求解nextval数组归结于两句话:
1.字符不相等,直接抄下来(指的是next和nextval相等)
2.字符相等,nextval = nextval

求解nextval数组代码:

void get_nextval(char *t, int nextval[]) 
//nextval数组长度应大于或等于strlen(t)
{ 
    int j, k;
    nextval[0] = k = -1; j = 1; 
    while(t[j]) 
    if(k == -1 || t[j - 1] == t[k]) 
    if(t[++ k] == t[j]) nextval[j ++] = nextval[k];
    else nextval[j ++] = k; 
    else k = nextval[k];
} //要点：k值仍然跟踪的是未改进的next[j]值

求解next数组代码:

void get_next(char *t, int next[]) 
//next数组长度应大于或等于strlen(t)
{ 
    int j, k;
    next[0] = k = -1; j = 1; 
    while(t[j]) 
    if(k == -1 || t[j - 1] == t[k]) next[j ++] = ++ k;
    else k = next[k];
}

KMP模式匹配

int index_kmp(char *s, char *t, int next[]) 
//要求next值已求取
{ 
    i = j = 0; 
    while(s[i] && (j == -1 || t[j])) 
    if(j == -1||s[i] == t[j]) { i ++; j ++; } 
    else j = next[j];
    if(!t[j]) return i - j;
    return -1; //返回-1表示匹配失败
}