【算法】KMP学习小结

学习kmp算法后的一些总结。本来没打算熬夜的结果搞到零点多。

在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可以在一个主文本字符串S内查找一个词w的出现位置。此算法通过运用对这个词在不匹配时本身旧包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。

——Wikipedia。

算法概述

简单来说，KMP算法就是用来解决字符串匹配问题的算法，即在一个主要字符串（称为主串）中寻找另一个字符串（称为模式串）是否存在的问题。

主要概念

学习KMP算法之前，首先要了解这个算法的一些重要概念。

失配

即“失去匹配”。指对于从l开始匹配模式串时，模式串第i位和主串第l + i位不相同，则称第i位失配。

next数组

在kmp算法中，预处理出的一个数组。next[i]表示第0位~第i - 1位中，前缀与后缀相同的部分最长长度(而不是回文)。同时，next[i]也表示着当模式串在第i位失配时，当前位置要跳转到哪一位才有可能重新匹配成功。

出于我的习惯，把数据从下标0开始放：则，next[i] = -1指从第0位第i - 1位的子字符串的相同前后缀不存在（即前后缀长度是0）。next[i]代表从第0位第i - 1位最大相同前后缀的长度 - 1，同样表示失配指针下标。

推导思路

在思考kmp算法之前，先来模拟一下朴素的扫描式字符串匹配算法：

朴素扫描

即模式串从前向后每次移动一个单位，每次移动后从前往后检查模式串和主串相应位置的字符是否相同，如果完全相同则匹配完成，失配则继续移动。

这种匹配方法的复杂度为O(nm)，显然，这种朴素算法有丶过于暴力了。我们需要优化它。

下面举出一个扫描过程的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

01234567890
ABCABABCABD <-主串
ABCABD <-模式串
------ 1
ABCABABCABD
 ABCABD
------ 2
ABCABABCABD
  ABCABD
------ 3
ABCABABCABD
   ABCABD
------ 4
ABCABABCABD
    ABCABD
------ 5
ABCABABCABD
     ABCABD

这五次移动中，中间的许多步骤是多余的。

再观察属于ABCABD的next[]:

1

int nxt[] = {-1, -1, -1, 0, 1, -1};

因为既然在第一步当中，D和A失配。那么他前方（不包括它本身）的子字符串与主串匹配。可以直接将当前位置跳转到next[5]，即0（-1表示触顶）的位置。则直接跳转到了最后一步，接着就可以匹配成功了。

虽然kmp算法不可能每次都准确地跳过所有地无用步骤，但是它的复杂度O(n + m)还是要比朴素算法优秀了不少。

kmp算法

通过上边的推导，可以发现：kmp算法的核心就是预处理出next数组。我们通过模式串自我比对来获取next数组。

通过巧妙地设置匹配游标k，可以快速地获取指定模式串的next[]数组。而实际上，预处理过程和正式的kmp过程思路和代码几乎完全一样。

具体实现

首先是预处理next数组的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

typedef long long ll;
const int MAXN = 1e6 + 5;
ll nxt[MAXN];

void getNext(string s)
{
	nxt[0] = -1; // -1 表示前后缀不存在
	int k = -1; // 模式串的匹配游标
	for (int i = 1; i < s.size(); i++)
	{
        //下一个数失配则更新本位的失配指针，k == -1则触顶
		while (k != -1 && s[k + 1] != s[i]) k = nxt[k];
		if (s[k + 1] == s[i]) k++; // 如果游标后可以继续得到相同的前后缀
		nxt[i] = k; // 更新next[]数组
	}
}

可以通过上边部分使用过的模式串ABCABD来简单模拟一下这个过程。这个过程实际上是寻找相同前后缀长度的过程，同时正得到了我们需要的next[]数组。

然后是kmp的过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void kmp(string s, string p)
{
	int k = -1;
	for (int i = 0; i < s.size(); i++)
	{
        // 下一位失配则移动游标 <=> 移动模式串
		while (k != -1 && p[k + 1] != s[i]) k = nxt[k];
		if (p[k + 1] == s[i]) k++; // 匹配成功，后移游标
		if (k == p.size() - 1)
		{
			// 找到某个匹配结果
			k = nxt[k]; // 继续向后匹配
			/// <custom_code>
				cout<<i - p.size() + 2<<endl; // 输出模式串开始位置
				// +2分别是位置坐标补正和减法补正:wq
			/// </custom_code>
		}
	}
}

其中<custom_code>中间是自定义的代码。一般的kmp题目输出要求可以再这里实现，这里输出的是每一个匹配成功的主串起始位置的下标。

总结

简单来讲，kmp算法就是模式串先自己和自己搞一遍，在和主串搞一遍（不）。

在纸上模拟之后就可以发现这个next数组的真正用途，接着就可以豁然开朗，从而理解这个过程。

kmp算法是AC自动机的基础知识点。AC自动机本质上是kmp算法思想和tire树结构的一种结合（但是对我这种菜鸡来说还是难炸了。

以上就是冻葱Tewi的kmp算法学习小结！