算法—KMP

发表于 分类于 ， 阅读次数： Disqus： 本文字数： 3k 阅读时长 ≈ 3 分钟

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

  • 初步涉及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];
        }
      }
    }