KMP

KMP 是在线求 border 数组（$\pi$ 函数），也就是每个前缀中最长公共前后缀的长度。

Z 函数

Z 函数是每个后缀和整个数组的 LCP，是离线算法。

但是用 KMP 求 Z 函数可以做到在线。只需要在跳 $\pi$ 函数的时候同时记录下当前需要确定的 $z_i$ 的所有 $i$ 即可。