KMP

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

求周期（border 套 border）

题目：P3435 - [POI 2006] OKR-Periods of Words

周期指的是 $s_{i+p}=s_i$，不是循环节。实际上求的是最短公共前后缀的长度。只需要不停地跳 border 直到 border 为 $0$（没有更小的公共前后缀），此时长度即为所求。

关键：${\pi }_{{\pi }_i}$ 是 $i$ 的次长公共前后缀。

border 上 DP

题目：P3426 - [POI 2005] SZA-Template

关键：设 $d{p}_i$ 为 $i$ 处的待求值。可以从 $d{p}_{{\pi }_i}$ 转移。

Z 函数

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

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