Z 函数

即 \(\forall i\)，求 \(z_i=|\operatorname{lcp}(s,s[i:n])|\)

考虑类似 Manacher，用增量法求解。

考虑对于一个 \(i\)，称 \([i,i+z_i-1]\) 为 \(i\) 的匹配段，记为 \([l,r]\)，考虑最大的 \(r\) 对应的匹配段

• \(i>r\)，此时直接暴力匹配
• \(i\leq r\)，则 \(s[l:r]=s[1:r-l+1]\)，故 \(s[i:r]=s[i-l+1:r-l+1]\)，则 \(z_i\geq \min(z_{i-l+1},r-i+1)\)，若 \(z_{i-l+1}\leq r-i+1\) 则继续暴力。注意到 \(r\) 只会增加，所以复杂度 \(\mathcal O(n)\)