字符串匹配到底有多痛？为什么我们一定要学KMP

我们以洛谷平台上的一道题为例。

在日常字符串处理场景中，模式串匹配是高频刚需问题：给定长文本串s1、短模式串s2，找出s2在s1中所有出现的起始位置。
大家最先想到的，一定是暴力匹配算法：

• 主串逐个位置对齐模式串开头，逐个字符比对

• 一旦匹配失败，主串指针回退到下一位，模式串直接归零从头匹配

这种写法逻辑简单，但是在重复字符场景下会产生重复比对，时间复杂度最坏达到 $O(N\ast M)$。当字符串长度上万、几十万时，暴力算法会直接超时。

而今天我们学习的KMP算法，完美解决这个痛点：

1. 主串指针永远不回退，全程只单向遍历一次

2. 提前预处理模式串，得到next数组（本题要求的最长Border数组）

3. 匹配失败时，依靠历史匹配信息，精准跳转模式串指针，绝不重复比对

4. 整体时间复杂度严格 $O(N+M)$，线性时间最优解

一、前置必懂概念：字符串Border

本题明确定义了Border，这也是KMP算法的灵魂根基，必须彻底吃透。

1.1 Border严谨定义

对于一个字符串s，它的Border是满足以下全部条件的子串t：

1. t ≠ s（不能是字符串本身）

2. t 是s的前缀

3. t 同时也是s的后缀

举个例子
对于字符串 aabcaab 我们从第一个字符和最后一个字符开始比对，字符串第一个字符是a,最后一个字符是b，两个字符不相等，于是继续比较前两个字符和倒数两个字符，前两个字符是aa，倒数两个字符是ab，依旧不相等，继续比较。字符串前三个字符是aab，倒数三个字符也是aab，此时两字符串相等,aab既是字符串前缀也是后缀，把它记录下来，以此类推…
我们最终需要找出满足既是字符串前缀也是后缀的最长字符串长度（注意不能是字符串本身），对于此字符串最长字符串长度就是3。（也即是题目中的border）

1.2 Border和KMP的关系

匹配失败时，我们不需要让模式串从头重来。依靠当前前缀的最长Border，就可以直接把模式串跳转到对应位置，继续匹配。这就是KMP不回退主串、不重复比对的核心原理。

二、KMP算法第一步：预处理next数组（最长Border数组）

2.1 next数组定义

next数组存储的是不含当前字符，前面字符串前后缀最大匹配长度，我们这里规定next[0]=-1,next[1]=0

举个例子：
s1字符串 a a b a a b s
数组下标 0 1 2 3 4 5 6
next数组-1 0 1 0 1 2 3
怎么得来的呢？由于我们已经规定next[0]和next[1]的值了，因此我们从数组下标为2的位置开始，next数组下标为2之前的字符串为aa，由前面border的定义可知字符串前后缀最大匹配长度为1，因此存储到next数组中，以此类推得到next数组

简单说，next 数组存储的是「模式串当前前缀的最长 Border 长度」，而 Border 的核心作用就是 “复用已匹配的信息”，这也是为什么能从 next 数组指向的位置开始比较。
举个最简单的例子：模式串是 ABA，next 数组是 [-1,0,1]。假设我们用模式串匹配主串时，匹配到模式串最后一个 A（下标 2）时失败了 —— 这时候我们已经知道，模式串前 3 个字符（ABA）的最长 Border 是 1（也就是前缀 A 和后缀 A 相等）。
这就意味着，已经匹配过的后缀 A，和模式串开头的 A 是完全一样的，我们根本不用从头再比模式串的第一个 A（浪费时间），直接从 Border 长度对应的位置（也就是下标 1，B 的位置）开始比较就行。
再通俗点理解：你已经确认了 “后面的 A 和前面的 A 一样”，那之前比对过的 A 就不用再重复比对了，直接从 A 后面的字符（B）继续比，既省时间，又不遗漏匹配可能。
本质就是：next 数组帮我们记住了 “已经匹配成功的部分”，避免重复劳动，所以能直接从 next 数组存储的位置（最长 Border 对应的长度）开始新的比较。

2.2 C语言实现next数组

// 函数功能：构建KMP算法的next数组（最长Border数组）
// 参数说明：
// s2[]：传入的模式串（需要预处理的字符串）
// next[]：输出数组，用于存储每个前缀的最长Border长度
// m：模式串s2的长度（注意：此处m是字符串有效长度，不是数组下标上限）
void getnext(char s2[], int next[], int m)
{
	next[0] = -1;
	if (m == 1) {
		return;
	}
	next[1] = 0;
	int i = 2;//数组下标从2开始，i是当前要求next位置
	int cn = 0;//当前要和前一个字符比对的下标位置
	while (i <= m) {
	//情况1：当前字符（s2[i-1]）与cn指向的字符相等
  //说明：当前前缀的最长Border长度可以延长，cn先自增（更新Border长度），再赋值		  给next[i]，最后i自增（计算下一个位置）
		if (s2[i - 1] == s2[cn]) {
			next[i++] = ++cn;
		}
		//情况2：字符不相等，但cn > 0（还有回溯的可能）
		//说明：利用已有的next数组，让cn回溯到next[cn]（即当前cn对应的最长Border长度），避免重复比对
		else if (cn > 0) {
			cn = next[cn];
		}
		//情况3：字符不相等，且cn == 0（无法再回溯）
  // 说明：当前前缀没有合法Border，next[i]赋值为0，i自增计算下一个位置
		else {
			next[i++] = 0;
		}
	}
}

KMP算法第二步：KMP实现

int kmp(char s1[], char s2[], int next[], int n, int m)
{
	int x = 0;//s1中匹配的下标位置
	int y = 0;//s2中匹配的下标位置
	while (x < n && y < m) {//若是返回查找到所有位置while(x<n)即可
		if (s1[x] == s2[y]) {
			x++;
			y++;
		}
		else if (y == 0) {
			x++;
		}
		else {
			y = next[y];
		}
		if (y == m) {
			//若只用返回第一个位置
			return x - y;
			//若要返回查找到的所有位置
			//printf("%d\n", x - y);
			//y = next[y];
		}
	}
}