• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

开发技术 开发技术 2周前 (04-30) 7次浏览

前言

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数组的公式:

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

这种鸟公式傻子才用

正解:

  • 首先对于前两个: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

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

    aba

    [0, 1, 1]

  4. 求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]

  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

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

    abaab

    [0, 1, 1, 2, 2]

  6. 求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]

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

  8. 求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举个例子:

  1. nextval[1] = 0

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

    S:aa

    T:aXYYYYYY(X为非a的任意字符, Y为任意字符)

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

    aXYYYY

    aa

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

    因为从第三位开始都是X,故T有可能是aXaa……,也就能匹配成功,再根据我们上面假设的偏移量的定义,得到偏移量为0

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

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

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

    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}

  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];
    }
}

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


程序员灯塔
转载请注明原文链接:KMP(梅开三度之数据结构详解版
喜欢 (0)