算法—KMP


  • 记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.

  • 初步涉及KMP时,有些蒙蔽,还好遇到了 阮一峰 的讲解,才啃下来.博文图来自资料链接.

资料来源如下

  • 从头到尾彻底理解KMP(2014年8月22日版)
  • 如何更好的理解和掌握 KMP 算法? - 海纳的回答 - 知乎
  • 字符串匹配的KMP算法 阮一峰

KMP

暴力搜索

  • 搜索字符串时最常用的是暴力搜索,

    • 一个字符一个字符去比较,第一位相同,比较第二位
    • 遇到不同字符,目标字符指针后移一位,重复.
    • 直到遇到模式字符终止符.返回目标字符指针位置.
  • 以下是暴力搜素的C语言一个实现版本

    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
    int ViolentMatch(char* s, char* p)
    {
    int sLen = strlen(s);
    int pLen = strlen(p);

    int i = 0;
    int j = 0;
    while (i < sLen && j < pLen)
    {
    if (s[i] == p[j])
    {
    //①如果当前字符匹配成功(即S[i] == P[j]),则i++,j +
    i++;
    j++;
    }
    else
    {
    //②如果失配(即S[i]! = P[j]),令i = i - (j - 1) j = 0
    i = i - j + 1;
    j = 0;
    }
    }
    //匹配成功,返回模式串p在文本串s中的位置,否则返回-1
    if (j == pLen)
    return i - j;
    else
    return -1;
    }
  • 对暴力搜索而言,整个流程上改进空间不大,主要集中在当搜索过程.见示例

    • 1
    • 2
    • 3
    • 4
  • 可以看到整个搜索过程,最明显的一个缺陷是,搜索到模式字符串的中间很长一段了,遇到一个坏字符,目标字符串指针移位1.模式字符还是要从头开始比较,模式字符在上一轮坏字符之前的比较相当于白做了.

KMP算法

  • 当空格与D不匹配时,前面六个字符是"ABCDAB"已知。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置" j 移回已经比较过的位置,而是继续把它向后移。

  • 经过KMP处理六个字符已知字符串"ABCDAB"后,可以得到一个表格,对应模式字符串每一位可前移的位数.如图
    8

  • 于是整个过程优化如下.

    • 1
    • 2
    • 3
    • 但空格与D失配,其前一位 (B->2),所以 j=2
    • 5
    • 但空格与C依旧失配.其前一位 (B->0),所以 j=0
    • 6
  • 对应c代码变化如下

    • 最主要的变化是引入next[]数组(方便).

      因为c语言数组元素由0开始,上文的表格右移一位.0位填充-1.得到next数组.

    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
    int KMP(char * t, char * p)
    {
    int sLen = strlen(s);
    int pLen = strlen(p);

    int i = 0;
    int j = 0;
    while (i < sLen && j < pLen)
    {
    //①如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++
    if (j == -1 || s[i] == p[j])
    {
    i++;
    j++;
    }
    else
    {
    //②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]
    //next[j]即为j所对应的next值
    j = next[j];
    }
    }
    //匹配成功,返回模式串p在文本串s中的位置,否则返回-1
    if (j == pLen)
    return i - j;
    else
    return -1;
    }

部分匹配表(Partial Match Table),next[]数组

  • 这里大量摘录了如何更好的理解和掌握 KMP 算法? - 海纳的回答 - 知乎的答案.

  • 上文提及的表格即部分匹配表.

  • 字符串的前缀和后缀。

    • 前缀: 如果字符串A和B,存在A=BS,其中S是任意的非空字符串,那就称B为A的前缀。例如,”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”},我们把所有前缀组成的集合,称为字符串的前缀集合。
    • 后缀: 后缀A=SB, 其中S是任意的非空字符串,那就称B为A的后缀,例如,”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”},然后把所有后缀组成的集合,称为字符串的后缀集合。
    • 要注意的是,字符串本身并不是自己的后缀。
  • PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度,如图
    前后缀

  • 这里换一组字符串“abababca”说明next数组求法

  • 求next数组的过程完全可以看成字符串匹配的过程,即以模式字符串为主字符串,以模式字符串的前缀为目标字符串,一旦字符串匹配成功,那么当前的next值就是匹配成功的字符串的长度。

  • 具体来说,就是从模式字符串的第一位(注意,不包括第0位)开始对自身进行字符串搜索(KMP)。 在任一位置,能匹配的最长长度(j值)就是当前位置的next值。如下图所示。

  • 如图

    • 1
    • 2
    • 3
    • 4
    • 5
  • c语言实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    void GetNext(char* p,int next[])
    {
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1)
    {
    //p[k]表示前缀,p[j]表示后缀
    if (k == -1 || p[j] == p[k])
    {
    ++k;
    ++j;
    next[j] = k;
    }
    else
    {
    k = next[k];
    }
    }
    }
  • 流程(部分):

    • next[6]=4
    • p[6] != p[4]; k = next[4] = 2
    • p[6] != p[2]; k = next[2] = 0
    • p[6] != p[0]; k = next[0] = -1
    • k == -1; ++k; ++j; next[7]=k=0;
  • 回到字符串"ABCDAB",得到的next数组如下
    next

next[]数组改进

  • j 沿着next[]数组回溯时,可能产生一种情况是:连续几次回溯到的字符相同,即连续几次比较了模式字符串里相同的字符.

  • 如上一节流程部分.

    • p[4] p[2] p[0]都为元素a,实际只需要与 p[6] 比较一次即可.
  • 未避免这种情况,可以对next[]数组回溯链上,连续相同的字符合并,直接取前一个字符对应位置next[]数组的值.由此产生的数组叫nextval数组.

  • c代码实现:

    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
    void GetNextval(char* p,int next[])
    {
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1)
    {
    //p[k]表示前缀,p[j]表示后缀
    if (k == -1 || p[j] == p[k])
    {
    ++k;
    ++j;
    //
    if(p[k]==p[j])
    {
    next[j] = next[k];
    }
    else
    {
    next[j] = k;
    }
    }
    else
    {
    k = next[k];
    }
    }
    }