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

前言

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

1. next[1] = 0

2. next[2] = 1

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

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

5. 求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

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

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

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

手撕nextval数组

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

例如：

当匹配串与模式串在第四个位置失配时，指向模式串的 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举个例子：

1. nextval[1] = 0

2. 当第二个字符失配，说明第一个字符是完全相同

3. 第三个字符失配与第二个相同, nextval[3] = 0

4. 第四个字符失配与第二个相同, nextval[4] = 0

5. 当第五个字符失配时，说明前四个肯定完全相同，故：

法2：借助next数组求nextval

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

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

1. nextval[1] = 0
2. S[2] != S[next[2]], 故nextval[2] = next[2] = 1
3. S[3] = S[next[3]] ---> 跑到了第一个，故nextval[3] = 0
4. S[4] != S[next[4]]， 故nextval[4] = next[4] = 2
5. S[5] = S[next[5]] ---> S[next[5]] != S[next[next[5]]], 故S[5] = next[next[5]] = 1
6. S[6] != S[next[6]], 故 nextval[6] = next[6] = 3
7. S[7] = S[next[7]], 且跑到了第一个位置，故next[7] = 0
8. 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];
    }
}

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