kmp算法 next[]数组的两种求法

作者: 亚欧沙龙 | 来源:发表于2018-12-22 21:12 被阅读0次

kmp算法 next[]数组的两种求法
KMP算法
问答|KMP算法学习笔记
KMP算法理解
数据结构与算法14-字符串匹配与KMP
字符串匹配问题-KMP算法
28-实现 strStr()-KMP算法
kmp_algorithm
改进KMP算法
KMP实现

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) 对于上面的第一种解法

初始化


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