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 值”生成):
首先可以确定的是
next[0]
一定是-1
,那么k
的初始值一定是等于next[0]
的(也就是-1
)。那么,j
的初始值也便可以为1
(因为next[0] = -1
已经确定,只需要从next[1]
开始确定 next 数组即可[1])。使
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
,
0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
a | b | a | b | a | a | a |
-1 |
- (
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 |
- (
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 |
- (
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 |
- (
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 |
- (
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 |
- (
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; } } }
next[1]
也必定等于1
,那为什么j
不从2
开始呢?
很简单,万一子串只有一个字符怎么办?
懂了吧! ↩︎