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函数
如果你画一画可能就理解了（