KMP（梅开三度之数据结构详解版

2021 年 4 月 30 日
筆記
算法

前言

KMP算法是一种字符串匹配算法，其重中之重是next数组的构建，其代码的简洁与神奇使其广受关注。

但不难发现，acm中学到的KMP和数据结构里面学到的KMP并不一样o(︶︿︶)o

之前我写过acm版的KMP，戳这里

现在写一篇数据结构版的KMP，便于应对即将到来的数据结构考试（艹

手撕next数组

先来复习一下acm版next数组：next[i]是部分匹配值，也就是前缀和后缀的最长共有元素的长度

而数据结构版的next数组指的是当匹配失效的时候，匹配串的 j 指针应该指向的位置（即next[j]）

这两种本质上来说，失配的时候都是指向next[j]，但是由于acm输入的字符串的下标是从0开始，而数据结构都是从1开始，所有会有差别滴

这里主要介绍在考试的时候给你一个字符串时如何快速滴手撕next数组

先看一下next数组的公式：

这种鸟公式傻子才用

正解：

首先对于前两个：next[1] = 0; next[2] = 1;（注意，下标从1开始）
后面每一位的next值求解：根据前一位进行比较
- 将前一位的字符与前一位的next值作为下标对应的字符进行比较
- 相等，则该位的next值就是前一位的next值加上1
- 不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值
- 若找到第一位都不匹配，则改为的next值为1。

举个例子：abaabcac

next[1] = 0
next[2] = 1
求next[3] 则去判断前一位的字符与前一位的next对应的字符，发现不相同，此时已经匹配到了第一位，还不相同，则next值为1

S[2] != S[next[2]], 且匹配到了第一位，故next[3] = 1

aba

[0, 1, 1]
求next[4]则去判断前一位字符a 与前一位next[3] 对应的字符a比较，发现相同，则next[4] = next[3] + 1 = 2

S[3] = S[next[3]], 故S[4] = S[3] + 1 = 2

abaa

[0, 1, 1, 2]
求next[5] 则去判断前一位(4)的a与前一位(4)的next[4]对应的字符b相比，发现不同，就继续用前一位(4)的字符a 与 next[4]对应的字符的next值(2)对应的字符a比较，发现相同，则next[5] = next[next[4]] + 1, 也就是next[5] = next[2] + 1 = 2

S[4] != S[next[4]] —>. S[4] = S[next[next[4]]], 故 next[5] = next[next[4]] + 1 = 2

abaab

[0, 1, 1, 2, 2]
求next[6] 则去判断第五位的b与第五位的next值对应的字符b，发现相同，则next[6] = next[5] + 1

S[5] = S[next[5]], 故next[6] = next[5] + 1 = 3

abaabc

[0, 1, 1, 2, 2, 3]
求next[7] 则去判断第6位的c与第next[6]位对应的字符，发现不同，就拿第6位的c与第next[next[6]]对应的 a 相比，发现不同，且匹配到了第一位，故next[7] = 1

S[6] != S[next[6]]—>next[6] != S[next[next[6]]], 且next[next[6]] = 1,即匹配到第一位还不同，则next[7] = 1

abaabca

[0, 1, 1, 2, 2, 3, 1]
求next[8] 则去判断第7位的a 与 next[7]对应的a比较，发现相同，则next[8] = next[7] + 1

S[7] = S[next[7]], 故next[8] = next[7] + 1 = 2

abaabcac

[0, 1, 1, 2, 2, 3, 1, 2]

手撕nextval数组

nextval数组是对next数组的优化版

例如：

匹配串S：aaaab

模式串T：aaabaaaab

匹配串的 next[] = {0,1, 2, 3, 4}

当匹配串与模式串在第四个位置失配时，指向模式串的 i 是不变的，指向匹配串的 j 是需要变成next[j] ，就需要将 T[4] 与 S[3]进行比较，会发现，还是不同，就让指针 j 继续跳，一值下去，会发现 T[4] 与 S[3] S[2] S[1] 都进行了比较，但我们之间观察的话会发现，S[1] = S[2] = S[3] = S[4] = a，根据S[4] != T[4]，故S[1] 、S[2] 、S[3] 都不等于T[4]，相当于这三次比较毫无卵用，这就是next数组需要优化的地方，故提出了nextval数组来优化

手撕nextval数组有两个方法：

法1.试想法：

试想匹配串S与模式串T在第 i 位（1<= i <= S.size())失配时，看看在最优的情况下，匹配串的头能与模式串的尾能重叠的长度最大为多少，其实也就是偏移量（设S[1] 移动到 i + 1位置表示的偏移量为0，S[1] 移动到 i 位置表示的偏移量为1，以此类推）

拿aaaab举个例子：

nextval[1] = 0
当第二个字符失配，说明第一个字符是完全相同

S：aa

T：aXYYYYYY（X为非a的任意字符， Y为任意字符）

我们从T的第二位开始与S拿去比较：

aXYYYY

aa

由于X不为a，故匹配失败，继续从T的第三位开始与S进行匹配

因为从第三位开始都是X，故T有可能是aXaa……，也就能匹配成功，再根据我们上面假设的偏移量的定义，得到偏移量为0
第三个字符失配与第二个相同, nextval[3] = 0
第四个字符失配与第二个相同, nextval[4] = 0
当第五个字符失配时，说明前四个肯定完全相同，故：

S：aaaab

T：aaaaXYYYY……（X

同样的，我们从第二位开始比较，会发现：S[2] = T[2],S[3] = T[3],S[4] = T[4], 对于T[5] 他除了b以外都可以取，所以可以取a,则第五位也可以匹配，就匹配成功

aaaaXYYYYY

aaaab

此时偏移长度为4（偏移串：aaaa）

故nextval[5] = 4

法2：借助next数组求nextval

总的来说：不同则为next值，想同则继续往前比较，直到找到不同或第一位,跑到了第一个则为0

举个上面讲过的第一个的例子来解释：

abaabcac

next= {0, 1, 1, 2, 2, 3, 1, 2}

nextval[1] = 0
S[2] != S[next[2]], 故nextval[2] = next[2] = 1
S[3] = S[next[3]] —> 跑到了第一个，故nextval[3] = 0
S[4] != S[next[4]]，故nextval[4] = next[4] = 2
S[5] = S[next[5]] —> S[next[5]] != S[next[next[5]]], 故S[5] = next[next[5]] = 1
S[6] != S[next[6]], 故 nextval[6] = next[6] = 3
S[7] = S[next[7]], 且跑到了第一个位置，故next[7] = 0
S[8] != S[next[8]],故nextval[8] = next[8] = 2

对于这两种方法，个人感觉法二简单多辽，不过前提是得将next数组算出来，且必须要算的正确，不然直接凉凉(>_<)

这里再贴出next数组和nextval数组的代码：

void getnext(string s){
    s = " " + s;//因为next数组从1开始，串从0开始，所以加个空格前缀
    int i = 1, j = 0;
    nextt[1] = 0;
    while (i < s.size()) {
        if(j == 0 || s[i] == s[j]){
            nextt[++i] = ++j;
        }
        else j = nextt[j];
    }
}

void getnextval(string s){
    s = ' ' + s;//道理同上
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < s.size()) {
        if(j == 0 || s[i] == s[j]){
            ++i;++j;
            if(s[i] != s[j])nextval[i] = j;
            else nextval[i] = nextval[j];
        }
        else j = nextval[j];
    }
}

我绝对不是数据结构课上因为摸鱼没听课，才过来写博客滴⁄(⁄ ⁄ ⁄ω⁄ ⁄ ⁄)⁄

Tags: 算法

KMP（梅开三度之数据结构详解版

前言

手撕next数组

正解：