KMP 算法研究

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.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 算法，再来看这篇文章。

推荐视频讲解：KMP 算法工作原理——bilibili

1.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 数组的基本理论

2.1 Next 数组生成概述

2.1.1 算法一

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] 已经不存在，无法比较）！

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

1. 我们使 char* p = {"ababaaa"}，（j = 0）然后使 next[0] = -1，

0	1	2	3	4	5	6
a	b	a	b	a	a	a
-1

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

0	1	2	3	4	5	6
a	b	a	b	a	a	a
-1	0

3. （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。

0	1	2	3	4	5	6
a	b	a	b	a	a	a
-1	0	0

4. （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。

0	1	2	3	4	5	6
a	b	a	b	a	a	a
-1	0	0	1

5. （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。

0	1	2	3	4	5	6
a	b	a	b	a	a	a
-1	0	0	1	2

6. （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。

0	1	2	3	4	5	6
a	b	a	b	a	a	a
-1	0	0	1	2	3

7. （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。

0	1	2	3	4	5	6
a	b	a	b	a	a	a
-1	0	0	1	2	3	1

2.1.2 算法二

略略略…

2.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 数组修正的基本理论

3.1 Next 数组修正概述

3.1.1 为什么要修正？

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

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

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

索引	0	1	2	3	4
子串（P）	a	b	a	b	d
next	-1	0	0	1	2
nextval	-1	0	-1	0	2

Ⅰ）使用原 next 的 kmp 算法：

主串（S）	子串（P）	关键判断
ababcababd	ababd	===
ababcababd	ababd	===
ababcababd	ababd	===
ababcababd	ababd	===
ababcababd	ababd	=/=
ababcababd	ababd	next[4]=2
ababcababd	ababd	=/=
ababcababd	ababd	next[2]=0
ababcababd	ababd	=/=
ababcababd	ababd	===
…	…	===
ababcababd	ababd	===

Ⅱ）使用 nextval 的 kmp 算法：

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

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

3.1.2 如何修正

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

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

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

3.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;
}

六、补充

2023年07月09日
namespace KMP_STD
{
    internal class KMP
    {
        private const int MSG_KMP_MATCH_EXCEPTION = -1;     // 消息 —— 匹配错误
        public const bool FLAG_OPTIMIZE_NEXT = true;        // 标志 —— 生成 Next 数组时进行 Next 数组优化
        public const bool FLAG_NORMAL_NET = false;          // 标志 —— 生成 Next 数组时不进行 Next 数组优化

        public int[]? Next = null;

        // 生成 KMP Next 数组
        public bool GetNext(string P, bool WhetherToOptimize = FLAG_NORMAL_NET)
        {
            Next = new int[P.Length];

            // Next 数组前两位必为 -1 0, 所以只需要从第三位开始生成即可
            Next[0] = -1;
            Next[1] = 0;
            int j = 2, k = 0;

            try
            {
                while (j < P.Length)
                {
                    if (k == -1 || P[j - 1] == P[k])
                    {
                        if (FLAG_OPTIMIZE_NEXT == WhetherToOptimize)
                        {   // 优化 Next 生成算法 —— NextVal
                            ++k;

                            if (P[j] == P[k])
                                Next[j] = Next[k];
                            else
                                Next[j] = k;

                            j++;
                        }
                        else
                        {   // 普通 Next 生成算法 —— Next
                            Next[j] = ++k;
                            j++;
                        }
                    }
                    else
                    {
                        k = Next[k];
                    }
                }
            }
            catch (Exception e)
            {
                Console.WriteLine(e.ToString());

                return false;
            }

            return true;
        }

        // 字符串匹配算法逻辑
        public int Match(string P, string S)
        {
            int PIndex = 0,     // 主串遍历索引
                SIndex = 0,     // 字串遍历索引
                FirstPos = -1;  // 返回字串在主串第一次出现时的首字符位置索引值

            try
            {
                while (PIndex < P.Length)
                {
                    if (SIndex == -1 || P[PIndex] == S[SIndex])
                    {
                        PIndex++;
                        SIndex++;
                    }
                    else
                    {
                        SIndex = Next![SIndex];
                    }

                    // 检查是否匹配成功
                    if (SIndex == S.Length)
                    {
                        FirstPos = PIndex - S.Length;   // 返回匹配成功时字串第一次出现的首字母位置
                        break;
                    }
                }
            }
            catch (Exception e)
            {
                Console.WriteLine(e.ToString());
                return MSG_KMP_MATCH_EXCEPTION;
            }

            return FirstPos;
        }
    }
}

---

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