//next 数组求解
void get_next(SString T ,int next[])
{
    int i = 1 , j = 0;
    next[1] = 0;
    while(i < T.length)
    {
        if(j == 0 || T.ch[i] == T.ch[j])
        {
            i++ , j ++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

首先，我们来理解三个概念：

       前缀：除了字符串的最后一个字符外，所有的头部子串。

       后缀：除了字符串的第一个字符外，所有的尾部子串。

       部分匹配值： 前缀和后缀的最长相等前后缀长度。

       以‘abaabc’为例：

‘a’的前缀后缀都为空，最长相等前后缀长度为0。

‘ab’的前缀为{a}，后缀为{b}，交集为空，最长相等前后缀长度为0。

‘aba’的前缀为{a，ab}，后缀为{a，ba}，交集为{a}，最长相等前后缀长度为1。因为前缀和后缀有最长的相等的元素‘a’，‘a’的长度为1。

‘abaa’的前缀为{a，ab，aba}，后缀为{a，aa，baa}，交集为{a}，最长相等前后缀长度为1。

‘abaab’的前缀为{a，ab，aba，abaa}，后缀为{b，ab，aab，baab}，交集为{ab}，最长相等前后缀长度为2。

‘abaabc’的前缀为{a，ab，aba，abaa，abaab}，后缀为{c，bc，abc，aabc，baabc}，交集为空，最长相等前后缀长度为0。

因此，‘abaabc’部分匹配值为001120

对于这个部分匹配值的计算算出来不是next数组！！！

为了使用方便，我们可以将部分匹配值整体右移一位，在最左侧补一个‘-1’，舍去最右侧的数字，这样，匹配失败的元素对应位置对照自己的部分匹配值即可。即将‘abaabc’部分匹配值转变为-100112。我们就把转换后的数组称为next数组。

• 使用-1进行填充是因为当模式串第一个字符都没匹配上时需要将模式串整体向右移动一位，不需要计算模式串移动的位数。
• 将部分匹配值最右侧的数字舍去是因为永远不会用到它

  先求出部分匹配值，再进行右移，具体例子在上面讲解部分匹配值时已经讲过，这里不再赘述。我们要注意，在面对实际题目时，我们 一定要看清楚题目要求，是以-1开始，还是以0 开始，如果以0开始，就是在以-1开始的基础上给每个数字加1。

对于求abaabc的next数组，我们得到的next数组是-100112，同时加一后得到的next数组是011223，这两个结果都是正确的。

下面是使用 abaabcaba 作为主串，以及 aabca 作为模式串的 KMP 字符串匹配过程中，涉及到的所有数组的详细表格。