即 \(\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)\)