又是一个非常冷门的算法 awa,换个名字可能会认得——扩展KMP
emm…… 然后在信息期末考试的时候,给材料现学现做了(然而那道题的难点并不是Z算法)
# 引入
感觉跟 KMP 关系不大,倒跟 Manachar 的思想比较接近。
在 Z算法 中,对于一个字符串 $S=\{S_0,S_1,\cdots,S_{n-1}\}$ 定义了一个函数 $Z(i)$,表示以位置 $i$ 开始的 $S$ 的后缀 $T_i=\{S_i,S_{i+1},\cdots,S_{n-1}\}$ 与 $S$ 的最长公共前缀的长度。
其中特殊定义 $Z(0)=0$。
暂且不管这个函数有什么用,先看看这个函数怎么算的。
# Z-Algorithm
我觉得 Z算法 的发明者应该是忽然想到 Z函数,然后感觉用 Z函数 可以搞大事情……
研究过后得到了这个算法
考虑从左到右依次计算 $Z(i)$。
> Tab.
以下区间 $[L,R]$ 均表示 $S$ 中从 $L$ 到 $R$ 的子串。注意 $S$ 下标从 $0$ 开始!
定义“匹配段”表示 目前已经计算得到的、是 $S$ 的前缀的子串,然后维护当前右端点最大的匹配段 $[L,R]$。
然后计算 $Z(i)$:
$i>R$:直接暴力枚举计算 $Z(i)$。
$i\le R$:
因为 $[L,R]$ 是 $S$ 的前缀,也就是 $[L,R]=[0,R-L]$。那么一定有
$[i,R]=[i-L,R-L]$,于是可以利用 已经计算出的 $Z(i-L)$ 计算 $Z(i)$。
但是 $Z(i-L)$ 代表的子串并不一定等于 $[L,R]$,比如下面这样:也就是说:因为橙色位置可能不一样,所以 $Z(i)$ 不一定为 $Z(i-L)$。
这时候就要缩小,缩成这样就没问题了:
也就是说,我们可以确定 $Z(i)$ 至少为 $\min\{Z(i-L),R-i+1\}$(跟Manachar那种计算方式特别像)
然后 $Z(i)$ 可能还可以增大,于是继续暴力扩增 $Z(i)$。
# 代码实现
1 | void ZAlgorithm(){ |
# 时间复杂度
与 Manachar 非常类似,看起来很暴力,实际上是 $O(n)$ 的复杂度($n$ 是字符串长度)。
其实影响复杂度的只是 while
循环。
- 如果 $Z(i)=Z(i-L)$,那么一定不会进入
while
循环,因为下一个位置已经不匹配了; - 如果 $Z(i)=right-i+1$,那么会造成
right
指针的右移。设右移的次数是 $t$,那么这样移动的复杂度是 $O(t)$ 的; - 如果 $i>right$,那么可以把过程看成:先把
right
指针指向 i($O(1)$),然后归类到 2.。
于是 while
循环的均摊复杂度是 $O(\sum t)$,而 $\sum t\le n$,于是均摊复杂度是 $O(n)$。
如果只有 2. 情况,
right
就会从 0 挪到 n,那么 $\sum t= n$;但是有 3. 情况,right
会直接跳到i
位置,然后就会有 $\sum t<n$。合起来就是 $\sum t\le n$。
The End
Thanks for reading!
信息期末考试有点放水……