扩展kmp

扩展kmp(Z Algorithm)

引入

定义

Z函数

令Z(0) = 0

Z-box

这个过程就像啃老，老人死了就啃不了。
---------林老师

构建Z数组

• 若 $i$ 在已知的匹配区间内，即 $i \le r$ ，则可以利用Z值的对称性来初始化 $Z_i$
• 否则，从位置 $i$ 开始扩展，计算最长的公共前缀长度

快速求Z函数

• 若$z(i) \ne 0$，可以定义区间[i, i + z[i] - 1]为一个Z-Box, 显然，Z-box 对应的子串一定是整个字符串的前缀
• 从左往右枚举下标i，同时维护l和r，用[l, r]表示满足 $l \le i$且r最大的Z-Box。
• 综上，有3种情况，要分别考虑。

情况1 $i > r$

• 说明已经完全超过上一个Z-Box,任何一个新的Z-Box的r都会更大。
• 直接暴力比较，暴力计算出Z[i]
• 计算完成后，若Z(i) $\ne 0$ 更新l和r。

当你做不了富二代，啃不了老，你就努力做个富一代，让别人啃你。 -------林老师

例

代码

if(i > r){
	while(i + z[i] < n && s[z[i]] == s[i + z[i]])
		z[i]++;
	l = i;
	r = i + z[i] - 1;
}

情况2 $i \le r$ 且 $z[i - l] < r - i + 1$

• 已知$s[0, ...., r - 1]与s[l, ....., r]$相等，故$s[i - l, ....., r - l]与s[i, ......, r]$也相等。
• 所以，如果 $Z[i - 1] < r - i + 1$，说明从i开始匹配和从i - l开始匹配是一样的。
• 所以这个匹配一定会在离开$Z-Box$前停止
• 即$Z[i] = Z[i - l]$

else if(z[i - l] < r - i + 1)
	z[i] = z[i - l];

情况3 $i \le r$且$z [i - l] \ge r - i + 1$

• 说明整个$Z-Box$剩余部分都可以匹配，但后面的情况不确定，所以不能直接认定$Z[i] = Z[i - 1]$
• 但知道$Z[i]$至少有 $r - i + 1$， 后面进行暴力扩展$Z-Box$尽量延长。

else{
		z[i] = r - i + 1;
		while(i + z[n] < n && s[z[i] == s[i + z[i]]])
			z[i] ++;
		l = i;
		r = i + z[i] - 1;
	}

for(int i = 1, l = 0, r = 0; i < n; i ++){
	if(z[i - l] < r - i + 1)
		z[i] = z[i - l];
	else{
		z[i] = max(r - i + 1, 0);
		while(i + z[i] < n && s[z[i] == s[i + z[i]]])
			z[i] ++;
		l = i;
		r = i + z[i] - 1;
	}
}