[数据结构与算法]KMP算法详解，宏观思路+微观细节

KMP算法详解，宏观思路+微观细节

本文从三个大层面解释KMP算法，附有图表和公示，便于理解逻辑和分析
参考blog：【数据结构】串的模式匹配-KMP算法

一、背景

在匹配失败时，即s[i] != t[[j]，表示s中的第i个字符不等于t中的第j个字符，在这种情况下，我们可以知道：t中的前j个字符与s中的字符是匹配的，即式子（1）：
$s[i?j]\dots s[i?1]=t[0]\dots t[j?1](1)$

二、目标

KMP算法的目标是在t中寻找一个k，使得s[i] = t[k]。这样的话，当s[i] != t[j]时，便可以直接跳转到k，使s[i]与t[k]匹配。

但是，找出k的前提是：t中的前k个字符与s中从s[i]向前数k个字符是匹配的。

如图所示，即两红色区域内包含的字符相匹配，才能满足条件。
即：
$s[i?k]...s[i?1]=t[0]...t[k](2)$

三、求解k

将式（1）进行拆分，s部分分成2段，t部分也分成同样的2段，且分点为k，得：
$s[i?j]...s[i?k]...s[i?1]=t[0]...t[j?k]...t[j?1](3)$

那么显然，其对应段分别相等，即：
$s[i?k]...s[i?1]=t[j?k]...t[j?1](4)$

联合（2）（4）式可得：
$t[0]...t[k?1]=t[j?k]...t[j?1](5)$

四、公式含义

得到（5）式后，表示什么含义？如图

找出k，使得t[0]…t[k-1]与后k位字符相等，这里的k尽可能的大（1<=k<j）

五、next数组的求解

思路：将前k字符与前j个字符相匹配——>KMP问题
具体参见：【数据结构】串的模式匹配-KMP算法
代码如下：

void GereNext(SqString t,int *next)
{
	int j,k;
	j = 0; k = -1; next[0] = -1;//k用来扫描对比前面几个元素是否与j扫描的元素相同
	while (j < t.Length - 1)
	{
		if (k == -1 || t.data[j]==t.data[k])//当k=-1的时候说明到头了，j该往前走了。
		{
			j++;
			k++;
			next[j] = k;
		}
		else
			k = next[k];//这里为什么不是k=-1呢？因为k=-1和k=next[k]是一样的。
	}
}