KMP算法快速学习(手动求Next和Nextval数组步骤)(C实现万用代码)_next和nextval快速计算方法

写这篇文章,真的花了我很多功夫,希望能够对看到的大家有所帮助啦

可以重点只看下面标出的关键点,即可快速掌握KMP算法

KMP算法的作用

首先,KMP算法的作用是进行模式串的匹配

也就是对于一个已知的长字符串t,我们在其中找到,与模式串m完全相同的部分,并且返回相同部分的首数组标号

采用BF算法,能够非常直观求出匹配位置,但是由于指针回溯,进行了多余的比较,非常缓慢

这样就有了KMP算法的诞生

下文中,我们将待比较的字符串,存入下面这样的结构体中:

typedef struct Str
{
    char *ch;
    int length;
} Str;
1
2
3
4
5

next数组是什么+用KMP返回首次匹配位置

我们发现,可以减少BF算法比较次数的原因在于,BF算法中,每一次模式串的指针回移太长了

我们发现将如下图的指针i和j全部回移,归位,就会多进行很多无用的比较

我们之所以知道多余的回退是没有用的,是由模式串本身的特性决定的

我们已知,即使在出现不匹配时,不匹配处的左侧的字符串和主串对应位置,是相同,或者说匹配的.

就像上图中一样,进行到第三步的时候(图中标错了),前面的"ana"在主串和模式串中,都是相同的

我们可以考虑引入一个概念,也就是"最大公共前后缀",假设其位数为n位

也就是从该部分匹配串的第一位开始往后数n位,和此部分匹配串的最后一位开始往前数n位,两者完全相同

当然也会有"次大公共前后缀",但是如果是次大的话,就会出现回移过少,漏掉了可能性的情况

我们必须考虑最大的公共前后缀,让j指针回移最多,并且不会漏掉可能性,从而最大程度得节约步骤和考虑全面.这样一个最佳位置,其实就是最大公共前后缀的位数.

使用KMP的过程中,我们不回移i指针,仅仅将j指针回移到左边的"部分匹配串"的"最大公共前后缀"中的前缀的后一位的位置,重新继续与主串匹配

我们的next数组,与模式串的长度相同

其中,记录的就是当前位置左边的"部分匹配串"的最大公共子串长度n

也是j指针接下来要移动到的位置,在下图中已经说明了.

下面的代码是用上图中的第二种编号方法写出的:

int KMP(Str t, Str m)
{
    int next[m.length];
    getNext(m, next);
    int i = 0, j = 0;
    
    //循环体的条件是模式串和主串都没有遍历完成
    while (i < t.length && j < m.length)
    {
        //如果当前匹配成功,则主串和模式串均右移
        //特殊情况下,模式串指针指向-1,主串和模式串也都要后移
        if (j == -1 || t.ch[i] == m.ch[j])
            i++, j++;
        //如果没有匹配成功,则仅模式串回移到next数组中记录的最佳位置
        else
            j = next[j];
    }
    if (j == m.length)
        return i - j + 1; //这里返回的是主串的第几个开始成功匹配上
        // return i - j; //如果去掉+1则是表示开始匹配位置的数组标号
    else
        return -1; //没有匹配成功则返回-1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

next数组

void getNext(Str m, int next[]) //函数传参不允许引用数组
{
    int i = 0, j = -1;
    next[0] = -1;
    while (i < m.length - 1)
    {
        if (j == -1 || m.ch[i] == m.ch[j])
            next[++i] = next[++j] + 1;
        else
        {
            j = next[j];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

next数组改进为nextval数组

为什么要引入nextval数组呢?

其实上文中认为next数组就是模式串回退的最佳位置,其实是不对的

next数组中保存的是"当前位置左边部分匹配串"的"最大公共前后缀"的位数n或者是n-1(没有本质差别)

虽然next数组能用,它确实大大优化了模式串的后移位数,并且不会遗漏正确结果,但是它仍不是,效率最高的后移位置

为什么nextval数组更加优化了?

关键点!!!–具体做题和实操照这个做就够了,上面的原理看个大概就够了,这个例子则要反复熟悉,并且自己再多出几个题目反复练习验证,达到熟练

nextval数组是怎样得到的?

是在已知next数组的基础上,进行如下规则的判断得到的:

求next和nextval数组的例子如下,可以跟着线条多画几遍,就能够熟练了:

就拿下图中eg2中数据为例,在模式串为0位置处,next和nextval数组的值都必然是-1,这是默认不变的

• 首先,求next数组的方法就是:

首先以位置5为例:

要求出位置5的next值,必须要看位置5-1(=4)的next值

比较位置4的字符和next [ 4 ] (=1)位置的字符,如果相等,则5位置存入next[4]+1

若不等,则比较位置4字符和next [ next [ 4 ] ] (=0)的字符,如果相等,则存入next [ next [ 4 ] ] +1(=1)

然后,以位置7为例,考虑一种特殊情况,也就是到了最后也没有匹配成功的情况:

求7看6,'b’为标准,向前找到2号c,不匹配

再向前找到0号’a’,仍然不匹配,则直接返回(-1+1)=0

总结一下求next值方法!!!

前位字符为标准,next值作模串标号向前跳,匹配则返回该标号加1,不匹配继续向前跳,0号还不匹配直接返回0

• 在next数组的基础上,求nextval的方法就是:

以位置8为例:

求nextval数组,直接以当前位置的next值作为标号,向前跳一位,比较当前位和前跳位字符

1.匹配,则当前位nextval值,等于前跳位nextval值

2.不匹配,则当前为nextval值,直接等于当前位next值

总结一下求nextval值方法!!!

当前位字符为标准,next值为模串标号向前跳一位,匹配nextval值等于前跳位,不匹配当前位next值直接落下来

void getNextval(Str m, int nextval[])
{
    int i = 0, j = -1;
    int next[m.length];
    next[0] = -1;
    nextval[0] = -1;
    while (i < m.length - 1)
    {
        if (j == -1 || m.ch[i] == m.ch[j])
        {
            next[++i] = ++j;
            if (m.ch[i] == m.ch[next[i]])
                nextval[i] = nextval[next[i]];
            else
                nextval[i] = next[i];
        }
        else
            j = next[j];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

用KMP求出所有匹配位置

将匹配起始点结果存入P数组中

可以灵活根据需要,修改这段代码,可以参考以下例子:

https://blog.nowcoder.net/n/2dc728211ba84e8096a41196ee5c6506

调整之后,就能够存入符合特定要求的匹配串了

void KMP_Multi(Str t, Str m, int P[])
{
    int nextval[m.length];
    getNextval(m, nextval);

    int i = 0, j = 0;
    int R = 0;
    while (1)
    {
        while (i < t.length && j < m.length)
        {
            if (j == -1 || t.ch[i] == m.ch[j])
                i++, j++;
            else
                j = nextval[j];
        }
        if (j == m.length)
        {
            P[R++] = i - j;
            // ver1以下是从后续开始,不找包含重复的部分
            // /*
            i = i - j + m.length;
            j = 0;
            // */
            // ver2以下是找出所有的重复部分
            /*
            i = i - j + 1;
            j = 0;
            */
        }
        else
        {
            P[R] = -1;
            break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

代码的完整实现

关键点!!!–getNextval和KMP_Multi这两个函数,可以直接拿来,经过简单的修改,就能用于绝大多数的情况,如果能够做到完全理解并且默写,则KMP算法就算完全掌握了

#include "stdio.h"
typedef struct Str
{
    char *ch;
    int length;
} Str;

void getNextval(Str m, int nextval[])
{
    int i = 0, j = -1;
    int next[m.length];
    next[0] = -1;
    nextval[0] = -1;
    while (i < m.length - 1)
    {
        if (j == -1 || m.ch[i] == m.ch[j])
        {
            next[++i] = ++j;
            if (m.ch[i] == m.ch[next[i]])
                nextval[i] = nextval[next[i]];
            else
                nextval[i] = next[i];
        }
        else
            j = next[j];
    }
}

void KMP_Multi(Str t, Str m, int P[])
{
    int nextval[m.length];
    getNextval(m, nextval);

    int i = 0, j = 0;
    int R = 0;
    while (1)
    {
        while (i < t.length && j < m.length)
        {
            if (j == -1 || t.ch[i] == m.ch[j])
                i++, j++;
            else
                j = nextval[j];
        }
        if (j == m.length)
        {
            P[R++] = i - j;
            // ver1以下是从后续开始,不找包含重复的部分
            // /*
            i = i - j + m.length;
            j = 0;
            // */
            // ver2以下是找出所有的重复部分
            /*
            i = i - j + 1;
            j = 0;
            */
        }
        else
        {
            P[R] = -1;
            break;
        }
    }
}

int main()
{
    Str m = {.ch = "anan\0", .length = 4};
    Str t = {.ch = "baanananaanan\0", .length = 13};

    int nextval[m.length];
    getNextval(m, nextval);
    printf("nextval数组如下:\n");
    for (int i = 0; i < m.length; i++)
        printf("%d\t", nextval[i]);

    printf("\n");
    int P[100] = {0};
    KMP_Multi(t, m, P);
    printf("匹配成功的位置,记录如下:\n");
    int i;
    for (i = 0; P[i] != -1; i++)
        printf("%d\t", P[i]);
    printf("%d\n", -1);
    return 0;
}
/*
nextval数组如下:
-1      0       -1      0
匹配成功的位置,记录如下:
2       9       -1
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93