「学习笔记」Z 函数（扩展 KMP）

前置芝士：KMP 算法

正文

本文涉及的字符串下标以 \(0\) 为起点。

对于个长度为 \(n\) 的字符串 \(s\)。定义函数 \(z(i)\) 表示 \(s\) 和 \(s_{i\sim n-1}\)（即以 \(s_i\) 开头的后缀）的最长公共前缀（LCP）的长度。\(z\) 被称为 \(s\) 的 Z 函数。

特别地，\(z(0)=0\)。

所谓的 Z 函数其实就是国内 OIer 所说的 “扩展 KMP”。

求解 Z 函数的值有一个朴素算法，即直接按照 Z 函数的定义暴力求解：

inline vector<int> z_function_trivial(string s)
{
	int n=(int)s.size();
	vector<int>z(n);
	rep(i,1,n-1)
	{
		while(i+z[i]<n&&s[z[i]]==s[i+z[i]])
			++z[i];
	}
	return z;
}

显然，这样的时间复杂度是 \(O(n^2)\) 的。

但是这样的算法速度还是太慢了，我们考虑优化。

而优化的关键就在于，运用自动机的思想寻找限制条件下的状态转移函数，使得可以借助之前的状态来加速计算新的状态。

在该算法中，我们从 \(1\) 到 \(n-1\) 顺次计算 \(z(i)\) 的值（\(z(0)=0\)）。

在计算 \(z(i)\) 的过程中，我们会利用已经计算好的 \(z(0),z(1),\cdots,z(i-2)\)。

对于 \(i\)，我们称区间 \([i,i+z(i)-1]\) 是 \(i\) 的 匹配段，也可以叫作 Z-box。

算法的过程中我们维护右端点最靠右的匹配段。

为了方便，记作 \([l,r]\)。根据定义，\(s_{l\sim r}\) 是 \(s\) 的前缀。

在计算 \(z(i)\) 时我们保证 \(l\le i\)。初始时 \(l=r=0\)。

在计算 \(z(i)\) 的过程中：

• 如果 \(i\le r\)，那么根据 \([l,r]\) 的定义有 \(s_{i\sim r}=s_{i-l\sim r-l}\)，因此 \(z(i)\ge\min(z(i-l),r-l+1)\)。这时：
  • 若 \(z(i-l)<r-l+1\)，则 \(z(i)=z(i-l)\)。
  • 否则 \(z(i-l)\ge r-l+1\)，这时我们令 \(z(i)=r-l+1\)，然后暴力枚举下一个字符扩展 \(z(i)\) 直到不能扩展为止。
• 如果 \(i>r\)，那么我们直接按照朴素算法，从 \(s_i\) 开始比较，暴力求出 \(z(i)\)。
• 在求出 \(z(i)\) 后，如果 \(i+z(i)-1>r\)，我们就需要更新 \([l,r]\)，即令 \(l\gets i,r\gets i+z(i)-1\)。

可以访问 这个网站 来看 Z 函数的模拟过程。

inline vector<int> z_function(string s)
{
	int n=(int)s.size();
	vector<int>z(n);
	int l=0,r=0;
	rep(i,1,n-1)
	{
		if(i<=r&&z[i-l]<r-i+1)
			z[i]=z[i-l];
		else
		{
			z[i]=max(0,r-i+1);
			while(i+z[i]<n&&s[z[i]]==s[i+z[i]])
				++z[i];
		}
		if(i+z[i]-1>r)
		{
			l=i;
			r=i+z[i]-1;
		}
	}
	return z;
}

对于内层 while 循环，每次执行都会使得 \(r\) 向后移至少 \(1\) 位，而 \(r<n-1\)，所以总共只会执行 \(n\) 次。

对于外层循环，只有一遍线性遍历。

总时间复杂度为 \(O(n)\)。

END.