L
O
A
D
I
N
G

KMP 算法研究

KMP 字符串查找
算法之旅
发布日期:   2022-10-19
更新日期:   2022-10-21
文章字数:   3.5k
阅读次数:  

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

虽然 KMP 是基础算法，但是却有着一定的难度，往往理解其算法思路后也难以用代码具体实现。在初学算法的道路上，算是一块难啃的骨头。于是，我决定花些时间好好研究一下这个神奇的算法。

我们提前约定：
1. S(STR) 代表“主串”;
2. P(PATTERN) 代表“子串”;
3. NextVal 为 Next 数组修正后的数组;
4. 本篇文章从程序的实际角度出发，下标统一从 0 开始。

同时，我将声明：本文为了便于理解，将 KMP 算法分成模块进行讲解。

一、KMP 算法基本理论

1）KMP 算法概述

相较于暴力破解的 BF 算法，KMP 算法的优点在于对主串的遍历不会回溯。

所以，当我们给予一个长度为 N 的主串时，使用 KMP 算法的时间复杂度即为 O(N)。

之所以能做到这一点，全靠 Next 数组记录了当主串字符与子串字符不匹配时（s[i] != p[j]），子串索引（j）可以直接跳转的位置（j = next[j]）。然后，继续比较即可，直至匹配成功或者匹配失败。

可以通过下面的动画理解⬇⬇：

1. 这个动画中 next[] = {-1, 0, 0, 1}

2. 这个动画中 next[] = {-1, 0, 0, 0, 1, 2, 3}

当然，这么讲肯定很晦涩难懂，特别对于第一次接触的朋友。所以，我建议先去看看视频动画演示的 KMP 算法，在来看这篇文章。

2）代码实现 KMP 算法

int KMP(char* s, char* p)
{
  int pos = -1;  // 用于返回值，查找成功返回子串第一次在主串中出现时第一个字符的下标

  int s_len = strlen(s),  // 主串长度
    p_len = strlen(p);  // 子串长度

  int i = 0,  // 控制主串的索引
    j = 0;  // 控制子串的索引

  int* next = (int*)malloc(p_len * sizeof(int));  // 用 malloc 声明一个一维 next 数组

  if (next) 
  {
    getNext(p, next);  // 调用 getNext 函数，初始化 next 数组

    while (i < s_len)
    {
      if (j == -1 || s[i] == p[j])  // 如果“主串字符与子串字符相同”或“子串已返回到第一个字符（j = next[0] = -1）”
      {
        i++;
        j++;
      }
      else  // 主串字符与子串字符不相同
      {
        j = next[j];
      }

      if (j >= p_len)  // 子串遍历完成，已经全部匹配
      {
        pos = i - j;  // 获取子串第一次在主串中出现时第一个字符的下标
        break;  // 跳出循环
      }
    }

    free(next);  // 释放 next 数组的内存空间
  }
  
  return pos;
}

二、Next 数组的基本理论

1）Next 数组生成概述

Ⅰ）算法一

next 数组的生成主要有两种办法，我个人认为通过“最大共同元素长度”生成的方式没有通过“前一个字符的 next 值”生成的方式。所以，我主要讲解第二种算法，第一种大家可以去看别的文章。

推荐文章：kmp算法 next[]数组的两种求法

下面着重介绍第一种算法（通过“前一个字符的 next 值”生成）：

  1. 首先可以确定的是 next[0] 一定是 -1，那么 k 的初始值一定是等于 next[0] 的（也就是 -1）。那么，j 的初始值也便可以为 1（因为 next[0] = -1 已经确定，只需要从 next[1] 开始确定 next 数组即可[1]）。

  2. 使 k = next[j - 1]， 判断 p[j - 1] =?= p[k]：

    • 如果 p[j - 1] == p[k]，那么就使 next[j] = next[j - 1] + 1 = k + 1;
    • 如果 p[j - 1] != p[k]，那么就使 k = next[next[j - 1]] = next[k]，然后再次判断 p[j - 1] =?= p[k]：
      • 如果 p[j - 1] == p[k]，那么就使 next[j] = next[next[j - 1]] + 1 = k + 1;
      • 如果 p[j - 1] != p[k]，那么就使 k = next[next[next[j - 1]]] = next[k]，然后再次判断 p[j - 1] =?= p[k]：
        • …
        • 直到判断到 p[j - 1] == p[k] 或者 k == -1（此时 p[k] = p[-1] 已经不存在，无法比较）！

这样讲可能还是有些抽象，那么举个简单的例子：

我们使 char* p = {"ababaaa"}，

（j = 0）然后使 next[0] = -1，

0123456
ababaaa
-1



（j = 1）那么因为 k = next[j - 1] = next[0] = -1 ，
因为 p[k] = p[-1] 不存在，所以 next[j] = next[1] = k + 1 = 0。

0123456
ababaaa
-10



（j = 2）接着，k = next[j - 1] = next[1] = 0，
判断 p[j - 1] = p[1] = 'b' 与 p[k] = p[0] = 'a' 不相同。
所以，k = next[next[j - 1]] = next[k] = -1，
因为 p[k] = p[-1] 不存在，所以 next[j] = next[2] = k + 1 = 0。

0123456
ababaaa
-100



（j = 3）然后，k = next[j - 1] = next[2] = 0，
判断 p[j - 1] = p[2] = 'a' 与 p[k] = p[0] = 'a' 相等。
所以，next[j] = next[3] = k + 1 = 1。

0123456
ababaaa
-1001



（j = 4）接着，k = next[j - 1] = next[3] = 1，
判断 p[j - 1] = p[3] = 'b' 与 p[k] = p[1] = 'b' 相等。
所以，next[j] = next[4] = k + 1 = 2。

0123456
ababaaa
-10012



（j = 5）接着，k = next[j - 1] = next[4] = 2，
判断 p[j - 1] = p[4] = 'a' 与 p[k] = p[2] = 'a' 相等。
所以，next[j] = next[4] = k + 1 = 3。

0123456
ababaaa
-100123



（j = 6）接着，k = next[j - 1] = next[5] = 3，
判断 p[j - 1] = p[5] = 'a' 与 p[k] = p[3] = 'b' 不相等。
所以，k = next[next[j - 1]] = next[k] = next[3] = 1，
继续判断 p[j - 1] = p[5] = 'a' 与 p[k] = p[1] = 'b' 不相等。
所以，k = next[next[j - 1]] = next[k] = next[1] = 0，
继续判断 p[j - 1] = p[5] = 'a' 与 p[k] = p[0] = 'a' 相等。
所以，next[j] = next[4] = k + 1 = 1。

0123456
ababaaa
-1001231

Ⅱ）算法二

略略略…

2）代码实现 Next 数组生成

void getNext(char* p, int* next)
{
  int k = -1, // 初始化 k 值，以后这个值在循环初始时必须保证和 next[j - 1] 一致
    j = 1,  // 因为 next[0] 一定为 -1 ，所以直接从 j = 1 处开始
    len = strlen(p); // 子串的长度

  next[0] = -1; // next[0] 一定为 -1

  while (j < len)
  {
    if (k == -1 || p[j - 1] == p[k])  // 遍历到 next[0] 了或子串中 p[j - 1] == p[next[j - 1]]
    { // 注意这个顺序
      k++;
      next[j] = k;
      j++;
    }
    else
    {
      k = next[k];
    }
  }
}

三、Next 数组修正的基本理论

1）Next 数组修正概述

① 为什么要修正？

在开始介绍修正算法之前还是得说一下为什么要进行 next 数组修正。

那么，让我们来看一组例子：

主串（S）：ababcababd
子串（P）：ababd
next 数组及 nextval 数组：

索引01234
子串（P）ababd
next-10012
nextval-10-102

Ⅰ）使用原 next 的 kmp 算法：

主串（S）子串（P）关键判断
ababcababdababd===
ababcababdababd===
ababcababdababd===
ababcababdababd===
ababcababdababd=/=
ababcababdababdnext[4]=2
ababcababdababd=/=
ababcababdababdnext[2]=0
ababcababdababd=/=
ababcababdababd===
……===
ababcababdababd===

Ⅱ）使用 nextval 的 kmp 算法：

主串（S）子串（P）关键判断
ababcababdababd===
ababcababdababd===
ababcababdababd===
ababcababdababd===
ababcababdababd=/=
ababcababdababdnext[4]=2
ababcababdababd=/=
ababcababdababdnext[2] = -1
ababcababdababd===
……===
ababcababdababd===

这么一来，使用 nextval 在处理类似的子串时就能减少一些不必要的判断，从而提高效率！

② 如何修正

这个算法并不难，可以用一段伪代码来表示：

nextval[0] = next[0] = -1;

if p[i] =?= p[next[i]]
{
  if 相同（===）
  {
    则 nextval[i] = next[next[i]];
  }
  else 不同（=/=）
  {
    则 nextval[i] = next[i];
  }
}

2）代码实现 Next 数组修正

void getNextval(char* p, int* next)
{
  int i,
    len = strlen(p);

  for (i = 1; i < len; i++)
  {
    if (p[i] == p[next[i]])
      next[i] = next[next[i]];
    else
      next[i] = next[i];
  }
}

四、KMP 算法的完整代码（理解版）

#include <stdio.h>
#include <malloc.h>
#include <string.h>

void getNext(char* p, int* next)
{
  int k = -1, // 初始化 k 值，以后这个值在循环初始时必须保证和 next[j - 1] 一致
    j = 1,  // 因为 next[0] 一定为 -1 ，所以直接从 j = 1 处开始
    len = strlen(p); // 子串的长度

  next[0] = -1; // next[0] 一定为 -1

  while (j < len)
  {
    if (k == -1 || p[j - 1] == p[k])
    {
      k++;
      next[j] = k;
      j++;
    }
    else
    {
      k = next[k];
    }
  }
}

int KMP(char* s, char* p)
{
  int pos = -1;  // 用于返回值，查找成功返回子串第一次在主串中出现时第一个字符的下标

  int s_len = strlen(s),  // 主串长度
    p_len = strlen(p);  // 子串长度

  int i = 0,  // 控制主串的索引
    j = 0;  // 控制子串的索引

  int* next = (int*)malloc(p_len * sizeof(int));  // 用 malloc 声明一个一维 next 数组

  if (next) 
  {
    getNext(p, next);  // 调用 getNext 函数，初始化 next 数组

    while (i < s_len)
    {
      if (j == -1 || s[i] == p[j])  // 如果“主串字符与子串字符相同”或“子串已返回到第一个字符（j = next[0] = -1）”
      {
        i++;
        j++;
      }
      else  // 主串字符与子串字符不相同
      {
        j = next[j];
      }

      if (j >= p_len)  // 子串遍历完成，已经全部匹配
      {
        pos = i - j;  // 获取子串第一次在主串中出现时第一个字符的下标
        break;  // 跳出循环
      }
    }

    free(next);  // 释放 next 数组的内存空间
  }
  
  return pos;
}

int main(int argc, char* argv[])
{
  char  s[] = { "abcabcabcdefsdjklasjseayjllasdn" },
      p[] = { "seayj" };
  printf("pos=%d\n", KMP(s, p));
  return 0;
}
#include <stdio.h>
#include <malloc.h>
#include <string.h>

void getNextval(char* p, int* next)
{
  int i,
    len = strlen(p);

  for (i = 1; i < len; i++)
  {
    if (p[i] == p[next[i]])
      next[i] = next[next[i]];
    else
      next[i] = next[i];
  }
}

void getNext(char* p, int* next)
{
  int k = -1, // 初始化 k 值，以后这个值在循环初始时必须保证和 next[j - 1] 一致
    j = 1,  // 因为 next[0] 一定为 -1 ，所以直接从 j = 1 处开始
    len = strlen(p); // 子串的长度

  next[0] = -1; // next[0] 一定为 -1

  while (j < len)
  {
    if (k == -1 || p[j - 1] == p[k])
    {
      k++;
      next[j] = k;
      j++;
    }
    else
    {
      k = next[k];
    }
  }
}

int KMP(char* s, char* p)
{
  int pos = -1;  // 用于返回值，查找成功返回子串第一次在主串中出现时第一个字符的下标

  int s_len = strlen(s),  // 主串长度
    p_len = strlen(p);  // 子串长度

  int i = 0,  // 控制主串的索引
    j = 0;  // 控制子串的索引

  int* next = (int*)malloc(p_len * sizeof(int));  // 用 malloc 声明一个一维 next 数组

  if (next) 
  {
    getNext(p, next);  // 调用 getNext 函数，初始化 next 数组

    getNextval(p, next);

    while (i < s_len)
    {
      if (j == -1 || s[i] == p[j])  // 如果“主串字符与子串字符相同”或“子串已返回到第一个字符（j = next[0] = -1）”
      {
        i++;
        j++;
      }
      else  // 主串字符与子串字符不相同
      {
        j = next[j];
      }

      if (j >= p_len)  // 子串遍历完成，已经全部匹配
      {
        pos = i - j;  // 获取子串第一次在主串中出现时第一个字符的下标
        break;  // 跳出循环
      }
    }

    free(next);  // 释放 next 数组的内存空间
  }
  
  return pos;
}

int main(int argc, char* argv[])
{
  char  s[] = { "abcabcabcdefsdjklasjseayjllasdn" },
      p[] = { "seayj" };
  printf("pos=%d\n", KMP(s, p));
  return 0;
}

五、KMP 算法代码（简洁版）

void getNextval(char* p, int* next)
{
  int k = -1, // 初始化 k 值，以后这个值在循环初始时必须保证和 next[j - 1] 一致
    j = 1,  // 因为 next[0] 一定为 -1 ，所以直接从 j = 1 处开始
    len = strlen(p); // 子串的长度

  next[0] = -1; // next[0] 一定为 -1

  while (j < len)
  {
    if (k == -1 || p[j - 1] == p[k])
    {
      k++;

      // next 数组修正
      if (p[j] == p[k])
        next[j] = next[k];
      else
        next[j] = k;

      j++;
    }
    else
    {
      k = next[k];
    }
  }
}

int KMP(char* s, char* p)
{
  int pos = -1;  // 用于返回值，查找成功返回子串第一次在主串中出现时第一个字符的下标

  int s_len = strlen(s),  // 主串长度
    p_len = strlen(p);  // 子串长度

  int i = 0,  // 控制主串的索引
    j = 0;  // 控制子串的索引

  int* next = (int*)malloc(p_len * sizeof(int));  // 用 malloc 声明一个一维 next 数组

  if (next) 
  {
    getNextval(p, next);

    while (i < s_len)
    {
      if (j == -1 || s[i] == p[j])  // 如果“主串字符与子串字符相同”或“子串已返回到第一个字符（j = next[0] = -1）”
      {
        i++;
        j++;
      }
      else  // 主串字符与子串字符不相同
      {
        j = next[j];
      }

      if (j >= p_len)  // 子串遍历完成，已经全部匹配
      {
        pos = i - j;  // 获取子串第一次在主串中出现时第一个字符的下标
        break;  // 跳出循环
      }
    }

    free(next);  // 释放 next 数组的内存空间
  }
  
  return pos;
}

  1. next[1] 也必定等于 1，那为什么 j 不从 2 开始呢？
    很简单，万一子串只有一个字符怎么办？
    懂了吧！ ↩︎

文章作者: SeaYJ
文章链接: https://seayj.cn/articles/99ba/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 SeaYJ !
KMP 字符串查找
赏
评论
  目录