KMP 算法学习笔记

问题引入

给出两个字符串 \(s1\) 和 \(s2\)，求出 \(s2\) 在 \(s1\) 中所有出现的位置（出现指 \(s1\) 中存在子串与 \(s2\) 完全相同）。

朴素暴力

不详细介绍，容易发现时间复杂度不优秀。

KMP 算法

思想

在朴素暴力中我们可以发现有很多匹配是不需要再次从头开始重新匹配的，举个例子：

ABABC
ABC

在匹配到第三位时发现失配，朴素做法即转到下一位重新从头匹配，当我们可以发现 AB 是重复的，可以直接从 \(s2\) 的第三位开始继续匹配（注意是 \(s2\)），从而提高效率，这就是 KMP算法的核心思想。

实现

我们可以定义一个 \(next\) 数组，我们先不用知道它是怎么来的，先知道它可以表示失配后可以跳过的字符数。

如：

ABABABCAA
ABABC

\(next\) 数组为 0 0 1 2 0。

我们定义 \(i\) 表示 \(s1\) 上的指针，\(j\) 表示 \(s2\) 上的指针，可以发现在匹配到第五位时会失配，此时读取失配上一位的 \(next\) 数组的值为 2，也就表示可以跳过两位匹配，则 \(j\) 赋值为 2（假定字符串下标从 \(0\) 开始），接着往下匹配直至匹配结束。

代码：

void KMP()
{
	int i=0,j=0;
	while(i<len1)
	{
		if(s1[i]==s2[j])i++,j++; // 匹配成功
			elif(j>0)j=Next[j-1]; // 匹配失败则跳过一些字符
				else i++; // s2 的第一个字符就失配
		if(j==len2)cout<<i-j+1<<"\n"; // 匹配成功
	}
}

接下来考虑 \(next\) 数组的计算。