求next数组详解
前缀、后缀、部分匹配值
"前缀"指除了最后一个字符以外，字符串的所有头部组合；
"后缀"指除了第一个字符以外，字符串的所有尾部组合。
“部分匹配值”是"前缀"和"后缀"的最长的共有元素的长度
以"abcdabd"为例
－ "a"的前缀和后缀都为空集，共有元素的长度为0；
－ "ab"的前缀为[a]，后缀为[b]，共有元素的长度为0；
－ "abc"的前缀为[a, ab]，后缀为[bc, c]，共有元素的长度0；
－ "abcd"的前缀为[a, ab, abc]，后缀为[bcd, cd, d]，共有元素的长度为0；
－ “abcda"的前缀为[a, ab, abc, abcd]，后缀为[bcda, cda, da, a]，共有元素为"a”，长度为1；
－ “abcdab"的前缀为[a, ab, abc, abcd, abcda]，后缀为[bcdab, cdab, dab, ab, b]，共有元素为"ab”，长度为2；
－ "abcdabd"的前缀为[a, ab, abc, abcd, abcda,abcdab]，后缀为[bcdabd, cdabd, dabd, abd, bd,d]，共有元素的长度为0。
部分匹配（Partial Match，PM）表
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| PM值 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
next数组求解方法
已知串T=“ababaaababaa”;
一、模式串的下标从0开始，此种方式的next数组求解方式：
此种方式的next数组就是上述PM值右移一位，空出的下标为0的位置赋值为-1（此处的-1是为了方便判断，也可以是其他值，自己斟酌即可）
下面从代码的角度讲述一下求解next[]的思路：
1、首先可以确定 next[0] = -1; next[1] = 0; 后面求解每一位的next值时，根据前一位进行比较。
2、从第三位开始，也就是从T[2]开始，比较前一位元素与其next值对应的元素是否相同
3、若相同，则所求next值就等于前一位元素对应的next值 +1
4、若不同，则向前继续寻找next值对应的元素与前一位进行比较，直到找到与前一位元素相同的元素，
若找到，则找到的这个位置的next值+1 就是我们所求的next值
5、若直到第一个元素，都没有找到与前一位元素相同的元素，则所求next值为0
1、可以确定前两位的值：next[0] = -1 ,next[1] = 0;
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | -1 | 0 |
2、看第三位，也就是T[2]，看T[2]的前一位T[1]对应元素是b，T[1]所对应的next值是0，0对应的元素是a，b与a不同，继续向前寻找next值，也就是找T[0]的next值为-1，表示T[1]之前没有找到与自身相等的元素，则第三位T[2]=a的next值为0，也就是next[2]=0
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | -1 | 0 | 0 |
3、看第四位，也就是T[3]，看T[3]的前一位T[2]对应元素是a，T[2]所对应的next值是0，0对应的元素是a，a与a相同，则T[3]对应的next值就是T[2]的next值+1 ，next[3] = 1；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | -1 | 0 | 0 | 1 |
4、看第五位，也就是T[4]，看T[4]的前一位T[3]对应元素是b，T[3]所对应的next值是1，1对应的元素是b，b与b相同，则T[4]对应的next值就是T[3]的next值+1 ，next[4] = 2；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | -1 | 0 | 0 | 1 | 2 |
5、看第六位，也就是T[5]，看T[5]的前一位T[4]对应元素是a，T[4]所对应的next值是2，2对应的元素是a，a与a相同，则T[5]对应的next值就是T[4]的next值+1 ，next[5] = 3；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | -1 | 0 | 0 | 1 | 2 | 3 |
6、看第七位，也就是T[6]，看T[6]的前一位T[5]对应元素是a，T[5]所对应的next值是3，3对应的元素是b，a与b不同，则向前继续寻找next值，找到T[3]对应的next值是1，1对应的元素是b，a与b不同，继续向前寻找next值，T[1]对应的next值是0，0对应的元素是a，a与a相同，则T[6]对应的next值就是T[1]的 next值 +1，next[6] = 1；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 |
7、看第八位，也就是T[7]，看T[7]的前一位T[6]对应元素是a，T[6]所对应的next值是1，1对应的元素是b，a与b不同，则向前继续寻找next值，T[1]对应的next值是0，0对应的元素是a，a与a相同，则T[7]对应的next值就是T[1]的 next值 +1，next[7] = 1；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 |
8、看第九位，也就是T[8]，看T[8]的前一位T[7]对应元素是b，T[7]所对应的next值是1，1对应的元素是b，b与b相同，则T[8]对应的next值就是T[7]的 next值 +1，next[8] = 2；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 |
9、看第十位，也就是T[9]，看T[9]的前一位T[8]对应元素是a，T[8]所对应的next值是2，2对应的元素是a，a与a相同，则T[9]对应的next值就是T[8]的 next值 +1，next[9] = 3；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 |
10、看第十一位，也就是T[10]，看T[10]的前一位T[9]对应元素是b，T[9]所对应的next值是3，3对应的元素是b，b与b相同，则T[10]对应的next值就是T[9]的 next值 +1，next[10] = 4；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 |
11、看第十二位，也就是T[11]，看T[11]的前一位T[10]对应元素是a，T[10]所对应的next值是4，4对应的元素是a，a与a相同，则T[11]对应的next值就是T[10]的 next值 +1，next[11] = 5；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
二、模式串下标从1开始，此种方式的next数组求解方式
此种方式的next数组就是上述PM值右移一位，空出的下标为0的位置赋值为-1，然后所有值整体+1得到next数组
下面从代码的角度讲述一下求解next[]的思路：
1、首先可以确定 next[1] = 0; next[2] = 1 ; 后面求解每一位的next值时，根据前一位进行比较。
2、从第三位开始，也就是从T[3]开始，比较前一位元素与其next值对应的元素是否相同
3、若相同，则所求next值就等于前一位元素对应的next值 +1
4、若不同，则向前继续寻找next值对应的元素与前一位进行比较，直到找到与前一位元素相同的元素，
若找到，则找到的这个位置的next值+1 就是我们所求的next值
5、若直到第一个元素，都没有找到与前一位元素相同的元素，则所求next值为1
1、可以确定前两位的值：next[1] = 0 ,next[2] = 1;
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | 0 | 1 |
2、看第三位，也就是T[3]，看T[3]的前一位T[2]对应元素是b，T[2]所对应的next值是1，1对应的元素是a，b与a不同，继续向前寻找next值，也就是找T[1]的next值为0，0没有对应的元素，表示没有找到与T[2]也就是b相等的元素，则第三位T[3]的next值为1，也就是next[3]=1
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | 0 | 1 | 1 |
3、看第四位，也就是T[4]，看T[4]的前一位T[3]对应元素是a，T[3]所对应的next值是1，1对应的元素是a，a与a相同，则T[4]对应的next值就是T[3]的next值+1 ，next[4] = 2；
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | 0 | 1 | 1 | 2 |
4、看第五位，也就是T[5]，看T[5]的前一位T[4]对应元素是b，T[4]所对应的next值是2，2对应的元素是b，b与b相同，则T[5]对应的next值就是T[4]的next值+1 ，next[5] = 3；
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | 0 | 1 | 1 | 2 | 3 |
5、看第六位，也就是T[6]，看T[6]的前一位T[5]对应元素是a，T[5]所对应的next值是3，3对应的元素是a，a与a相同，则T[6]对应的next值就是T[5]的next值+1 ，next[6] = 4；
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | 0 | 1 | 1 | 2 | 3 | 4 |
6、看第七位，也就是T[7]，看T[7]的前一位T[6]对应元素是a，T[6]所对应的next值是4，4对应的元素是b，a与b不同，则向前继续寻找next值，找到T[4]对应的next值是2，2对应的元素是b，a与b不同，继续向前寻找next值，T[2]对应的next值是1，1对应的元素是a，a与a相同，则T[7]对应的next值就是T[2]的 next值 +1，next[7] = 2；
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | 0 | 1 | 1 | 2 | 3 | 4 | 2 |
7、看第八位，也就是T[8]，看T[8]的前一位T[7]对应元素是a，T[7]所对应的next值是2，2对应的元素是b，a与b不同，则向前继续寻找next值，T[2]对应的next值是1，1对应的元素是a，a与a相同，则T[7]对应的next值就是T[2]的 next值 +1，next[8] = 2；
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 |
8、看第九位，也就是T[9]，看T[9]的前一位T[8]对应元素是b，T[8]所对应的next值是2，2对应的元素是b，b与b相同，则T[9]对应的next值就是T[8]的 next值 +1，next[9] = 3；
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 |
9、看第十位，也就是T[10]，看T[10]的前一位T[9]对应元素是a，T[9]所对应的next值是3，3对应的元素是a，a与a相同，则T[10]对应的next值就是T[9]的 next值 +1，next[10] = 4；
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 |
10、看第十一位，也就是T[11]，看T[11]的前一位T[10]对应元素是b，T[10]所对应的next值是4，4对应的元素是b，b与b相同，则T[11]对应的next值就是T[10]的 next值 +1，next[11] = 5；
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 |
11、看第十二位，也就是T[12]，看T[12]的前一位T[11]对应元素是a，T[11]所对应的next值是5，5对应的元素是a，a与a相同，则T[12]对应的next值就是T[11]的 next值 +1，next[12] = 6；
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 T | a | b | a | b | a | a | a | b | a | b | a | a |
| next[ ] | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
注意：这两种方式的细微差别，整体思路一致，注意next起始位置以及没有找到与前一位元素相同的元素时，next赋值问题，可赋值0或1，根据自己实际情况选择
代码实现
第一种：字符数组下标从0开始的代码如下：
/**
* 求next数组 ：字符数组下标从0开始
* next数组是模式串的部分匹配值整体右移一位，第一位赋值-1得到的数组
* 注意：若字符数组下标从1开始，则
* next数组即是 模式串的部分匹配值整体右移一位，第一位赋值-1，数组整体再+1 所得到的数组
*
*/
void getNext(char T[],int TLength) {
int next[TLength];
next[0] = -1;
printf("next[0] = %d \n", next[0]);
int i = 0, j = -1;//i表示数组下标，初始化为0；j表示next数组的值，初始化为-1
while (i < TLength -1) {
/**
* ①若j=-1表示没有找到相同的元素，所求next值应置为0
* ②若T[i] == T[j] 表示找到了相等的元素，此时找到的这个位置的next值+1就是所求next值
*/
if (j == -1 || T[i] == T[j]) {
i++;
j++;
next[i] = j;
printf("next[%d] = %d \n",i, next[i]);
}else{
j = next[j] ;
}
}
}
int main(){
char T[] = {'a','b','a','b','a','a','a','b','a','b','a','a'};
int TLength = 12;
getNext(T,12);
return 0;
}
测试结果：
next[0] = -1
next[1] = 0
next[2] = 0
next[3] = 1
next[4] = 2
next[5] = 3
next[6] = 1
next[7] = 1
next[8] = 2
next[9] = 3
next[10] = 4
next[11] = 5
第二种：字符数组下标从1开始的代码如下：
void getNext(char T[],int TLength) {
int next[TLength];
next[1] = 0;
printf("next[1] = %d \n", next[1]);
int i = 1, j = 0;//i表示数组下标，初始化为1；j表示next数组的值，初始化为0
while (i < TLength - 1) {
/**
* ①若j=0表示没有找到相同的元素，所求next值应置为1
* ②若T[i] == T[j] 表示找到了相等的元素，此时找到的这个位置的next值+1就是所求next值
*/
if (j == 0 || T[i] == T[j]) {
i++;
j++;
next[i] = j;
printf("next[%d] = %d \n",i, next[i]);
}else{
j = next[j] ;
}
}
}
int main(){
char T[] = {'*','a','b','a','b','a','a','a','b','a','b','a','a'};
int TLength = 13;
getNext(T,13);
return 0;
}
测试结果：
next[1] = 0
next[2] = 1
next[3] = 1
next[4] = 2
next[5] = 3
next[6] = 4
next[7] = 2
next[8] = 2
next[9] = 3
next[10] = 4
next[11] = 5
next[12] = 6
注意：这两种方式的细微差别，整体思路一致，注意next起始位置以及没有找到与前一位元素相同的元素时，next赋值问题，可赋值0或1，根据自己实际情况选择