定义 \(z_i\) 为 \([i,n)\) 与 \([0,n)\) 的 \(\mathrm {lcp}\)。
令当前 \([l,r]\) 与 \([1,r-l+1]\) 是匹配的，且为我们当前知道的 \(r\) 最大的区间（贪心）。现在我们递推求 \(z_i\)。（算法执行的过程中 \(i\leqslant l\)）。
根据这个匹配区间的定义，发现 \(z_i\leqslant \min(z_{i-l},r-i+1)\)。
分类讨论一下：
如果 \(z_{i-l}<r-i+1\) 且 \(i\leqslant r\)，那么显然，直接 \(z_i\leftarrow z_{i-l}\)。
否则，令 \(z_{i-l} \leftarrow \max(0,r-i+1)\)，暴力扩展即可。
类似 \(\mathrm {kmp}\) 的思想，利用均摊来证明时间复杂度：发现算法瓶颈在暴力扩展上，但是每次扩展都会使 \(r\leftarrow r+1\)，所以复杂度线性。
好的，既然你已经学会了 z 函数，让我们来看一道例题：[JSOI2019]节日庆典
又是一道蜜汁结论题。好吧其实还是勇敢点打一些复杂度不会算的做法。
又是动态维护答案区间啊。感觉这个 trick 挺优美的。