next数组两种求法

image.png

一、求法的文字描述

（1）第一种求法：根据前一个字符的next值求字符串记作 p；next 数组记作 next；

约定：

• 下标从 1 开始算，注意，不是从 0 开始算

• 字符串长度 >2

• 1）第一个字母的 next 值置 0 （nesxt[1] = 0），第二个字母的 next 值置 1（next[2] = 1）

• 2）从第 3 个开始，计算第 i 个位置的 next 值时，检查

p[i-1]== p[next[i-1]] ?（即这两个值是否相等）

解释：第 i 个位置的前一个位置的值（即 p[i-1]）与以该位置的next 值（即 next[i-1]）为下标的值（即 p[next[i-1]]）是否相等

若相等，则 next[i] = next[i-1] + 1

若不等，则继续往回找，检查

p[i-1]== p[next[next[i-1]]] ?

若相等，则 next[i] = next[next[i-1]] + 1

若不等，则继续往回找，直到找到下标为 1 还不等（即字符串第一个元素），直接赋值 next[i] = 1

（2）第二种求法：根据最大公共元素长度求

首先附上讲解的博文地址，里面有详细讲解

• 1）算出每一个字母前缀后缀的最大公共元素长度
• 2）最大公共元素长度整体向后移动一个长度，最前面的元素值填 -1，即为 next 数组的第一版本
• 3）（如果你需要的 next 数组第一个值为 -1，这步就可以省略了）next 数组的每一个值分别+1，即求得 next 数组。

前缀后缀的最大公共元素长度

• 前缀：即从第一个字母开始往后看到最后一个字母（不包括）为止的字符串的以第一个字母开头的子串(比如 "abab" 的前缀有a,ab,aba);

• 后缀：即从最后一个字母开始往前看到第一个字母（不包括）为止的字符串的以最后一个字符为末尾的子串(比如 "abab" 的后缀有b,ab,bab);

• 最大公共子串长度：也就是前缀和后缀拥有的相同子串的最大长度;

  以"abab"为例：

模式串的各个子串	前缀	后缀	最大公共元素长度
a	空	空	0
ab	a	b	0
aba	a,ab	a,ba	1
abab	a,ab,aba	b,ab,bab	2

二、实例

现在求字符串 P = "ababaaababaa"

(1) 对于上面的第一种解法

1. 初始化

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	0	1

2)求下标为3的字符的next值

• P[3-1] = P[2] = 'b';
• next[3-1] = next[2] = 1 ;
• P[next[3-1]] = P[1] = 'a';
• P[3-1] != P[next[3-1]] ，但是此时已经回溯到了第一个元素
• ∴ 直接P[3] = 1 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	0	1	1

3）求下标为 4 的字符的 next 值

• P[4-1] = P[3] = 'a';
• next[4-1] = next[3] = 1 ;
• P[next[4-1]] = P[1] = 'b';
• P[4-1] == P[next[4-1]] ;
• ∴ next[4] = next[4-1] + 1 = 2 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	0	1	1	2

4）求下标为 5 的字符的 next 值

• P[5-1] = P[4] = 'b';
• next[5-1] = next[4] = 2 ;
• P[next[5-1]] = P[2] = 'b';
• P[5-1] == P[next[5-1]] ;
• ∴ next[5] = next[5-1] + 1 = 3 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	0	1	1	2	3

5）求下标为 6 的字符的 next 值

• P[6-1] = P[5] = 'a';
• next[6-1] = next[5] = 3;
• P[next[6-1]] = P[3] = 'a';
• P[6-1] == P[next[6-1]];
• 所以 next[6] = next[6 - 1] + 1 = 4;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	0	1	1	2	3	4

6）求下标为 7 的字符的 next 值

• P[7-1] = P[6] = 'a';
• next[7-1] = next[6] = 4;
• P[next[7-1]] = P[4] = 'b';
• P[7-1] != P[next[7-1]] 并且现在还没有回溯到第一个,继续
• next[next[7-1]] = next[4] = 2;
• P[next[next[7-1]]] = P[2] = 'b';
• P[7-1] != P[next[next[7-1]]] 并且现在还没有回溯到第一个，继续
• next[next[next[7-1]]] = 1;
• P[next[next[next[7-1]]] = 'a';
• P[7-1] == P[next[next[next[7-1]]]];
• 所以next[7] = next[next[next[7-1]]] + 1 = next[2] + 1 = 2

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	0	1	1	2	3	4	2

7）求下标为 8 的字符的 next 值

• P[8-1] = P[7] = 'a';
• next[8-1] = next[7] = 2;
• p[next[8-1]] = P[2] = 'b';
• P[8-1] != P[next[8-1]] 并且现在还没有回溯到第一个,继续
• next[next[8-1]] = 1;
• P[next[next[8-1]]] = p[1] = 'a';
• P[8-1] == P[next[next[8-1]]];
• 所以next[8] = next[next[8-1]] + 1 = 2;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	0	1	1	2	3	4	2	2

8）求下标为 9 的字符的 next 值

• 推导过程同4) => next[10] = next[10-1] + 1 = 4 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	0	1	1	2	3	4	2	2	3

9）求下标为 10 的字符的 next 值

• 推导过程同4) => next[10] = next[10-1] + 1 = 4 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	0	1	1	2	3	4	2	2	3	4

10）求下标为 11 的字符的 next 值
推导过程同4) => next[11] = next[11-1] + 1 = 5 ;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	0	1	1	2	3	4	2	2	3	4	5

11）求下标为 12 的字符的 next 值
推导过程同4) => next[12] = next[12-1] + 1 = 6;

P	a	b	a	b	a	a	a	b	a	b	a	a
下标	1	2	3	4	5	6	7	8	9	10	11	12
next	0	1	1	2	3	4	2	2	3	4	5	6

(2) 对于上面的第二种解法

image.png

1）算出每一个字母前缀后缀的最大公共子串长度

P	a	b	a	b	a	a	a	b	a	b	a	a
前后缀最大公共子串长度	0	0	1	2	3	1	1	2	3	4	5

2）最大公共子串长度整体向后移动一个长度，最前面的元素值填 -1，即为 next 数组的第一版本

P	a	b	a	b	a	a	a	b	a	b	a	a
前后缀最大公共子串长度	-1	0	0	1	2	3	1	1	2	3	4	5

三、代码实现

void getnext(seqstring *p, int next[])
{
    int i, j;
    next[0] = -1;
    i = 0; j = -1;
    while (i < p->length)
    {
        if (j == -1 || p->str[i] == p->str[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
    for (i = 0; i < p->length; i++)
        printf("%d ", next[i]);
}

四、验证

#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 100

typedef struct {
    char str[MAXSIZE];
    int length;
}seqstring;

void getnext(seqstring *p, int next[])
{
    int i, j;
    next[0] = -1;
    i = 0; j = -1;
    while (i < p->length)
    {
        if (j == -1 || p->str[i] == p->str[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
    for (i = 0; i < p->length; i++)
        printf("%d ", next[i]);
}

int main()
    {
    int i, j = 0;
    seqstring str;
    str.length = 0;
    printf("请输入字符串的长度：\n");
    scanf("%d", &j);
    getchar();
    for (i = 0; i < j; i++)
    {
        scanf("%c", &str.str[i]);
        str.length++;
    }
    int next[] = { 0 };
    getnext(&str, next);
    system("pause");
    return 0;
}

234