Z algo

吃串串

Posted by ShanLunjiaJian's Blog on October 7, 2021

Z algo,或者说 扩展kmp,实在是非常经典。

大家第一次见到这个科技,可能是在 动物园,也可能是在 ARC058F。题外话是,我认为058F超越了一直到103的所有ARC传统题(意思是070F这个交互可能竞争最棒的ARC058~103题),所以我来学Z algo了。

Z algo用来求出一个字符串的\(z\)函数,其中\(z(i)\)的定义是\(s\)和它的后缀\(i\)的最长公共前缀(Longest Common Prefix, lcp)。

认为字符串是从\(1\)开始的。

前置知识 : Manacher。

算法

呃虽然它又叫扩展kmp,那大概只是因为它有一种和kmp类似的方法来处理 一个串和另一个串的一个后缀的lcp。Z的思想更类似于Manacher。

\(z(i)\)表示的是,\(s_{1,z(i)}\)和\(s_{i,i+z(i)-1}\)是相同的。假设现在要求\(z(j)\)了,并且\(i\leq j\leq i+z(i)-1\),就可以把\(j\)平移到\(j-i+1\)的位置,也就是说我们可以先用着\(z(j-i+1)\),然后尝试继续向后匹配。

然而这个相等的条件并不够强,也就是说\(z(j)\)并不总能取到\(z(j-i+1)\),如果它超过了\(z(i)\)那就不能保证后面还相等了。所以我们应该把\(z(j)\)初始化成\(\min(z(j-i+1),i+z(i)-j)\)。你已经看到了一个和Manacher类似的东西了!

我们在Z algo的过程中,维护当前\(i+z(i)-1\)最大的\(i\),记为\(l\),并记\(r=l+z(l)-1\)。那么我们对于每个\(i\),如果\(i\leq r\)则初始化\(z(i)=\min(z(i-l+1),r-i+1)\),否则\(z(i)=0\)。接下来向后爆力匹配,每次匹配成功都会让\(r\)增加,于是复杂度就是对的了。

注意\(z(1)\)需要特殊处理,它不能算入\(l,r\)中,为什么呢?因为你按照这个平移会移到自己,这就没意思了。

1
2
3
4
5
6
7
8
9
10
11
inline int min(int x,int y){ return x<y?x:y; }
inline void Z(int n,char *s,int *z)
{
	z[1]=n;
	for(int i=2,l=1,r=1;i<=n;i++)
	{
		if(i<=r) z[i]=min(z[i-l+1],r-i+1);
		while(i+z[i]<=n&&s[i+z[i]]==s[z[i]+1]) z[i]++;
		if(i+z[i]-1>r) r=i+z[i]-1,l=i;
	}
}

例题

那当然是ARC058F。

给一堆串,选一个子序列顺次接起来,要求最后长度为\(k\),并且字典序最小。\(n\leq 2000,k\leq 10^4,\sum\vert s\vert\leq 10^6\)。

神仙背包。

爆力dp就是设\(dp(i,j)\)表示用前\(i\)个串拼成长度为\(j\)的串,得到的字典序最小的串。复杂度是\(O(nk^2)\)。

考虑一件事情 : 如果\(dp(i,j_1)\)和\(dp(i,j_2)\)有不同的位,比如它们在\(l\)位前完全相同,但是\(dp(i,j_1)\)在第\(l\)位小于\(dp(i,j_2)\),那么后面不管接上什么,\(j_1\)都比\(j_2\)优,所以\(j_2\)就是无用的。

这里有一个问题,就是如果\(dp(i,j_1)\)本身不可能转移到\(dp(n,k)\),那么它有可能是随便拼出来的,我们要先倒着用长度跑一个可行性背包来筛去这些状态。

这个东西有什么用?它说明有用状态们一定都是最长的\(dp(i,j)\)的一个前缀。

考虑对于每个\(i\)的转移,我们维护一个长度递减的栈。每次转移完了当前的\(j\),拿着它和栈顶也就是最长的串比较,如果栈顶是它的前缀,那么我们直接把它入栈,否则就看两个串哪个更优,如果当前串不优那就扔掉它,否则就弹掉栈顶继续检查下一个。

然后发现因为是前缀,我们可以只记录每个\(i\)最长的串,其它的都可以用长度表示。

现在只有一个问题了,怎么比较两个串。弹栈和决策时的比较可以归为同一种,也就是比较两个 一个\(dp(i,...)\)加上一个\(s_i\)也可能不加 这样的东西,这里四个\(i\)是相等的。

当然可以二分hash!复杂度多个\(\log\),过不去。

考虑使用Z algo,然后就\(O(nk+\vert s\vert)\)了。

咋回事啊?众所周知,lcp等价于比较,因为我们知道lcp之后,lcp的下一个字符就不同了,它必然决定字典序。

我们考虑都加上\(s_i\)显然是最复杂的情况,所以考虑设两个串前面分别是\(a,b\),\(a\)是\(b\)的前缀,且\(a,b\)都是那一层最长的串\(c\)的前缀。那么

  • lcp不可能截止于前\(\vert a\vert\)个字符,因为\(a\)是\(b\)的前缀

  • 如果lcp截止于\(\vert a\vert+1,...,\vert b\vert\)个字符,问题变成求\(s_i\)的一个前缀和\(c\)的一个区间的lcp,它等价于求\(s_i\)和\(c\)的一个后缀的lcp(想一想为什么?)。这个怎么做呢?我们只需要把\(s_i\)和\(c\)连起来跑Z algo即可。

  • 如果lcp截止于\(\vert b\vert+1,...,\vert a\vert+\vert s_i\vert\)个字符,问题变成求\(s_i\)的一个后缀和它自己的lcp,它就是Z函数

如果你画一画可能就理解了(