一个字符串的所有 border 可以划分成不超过 $\log n$ 个不相交的等差数列，且在加字符时可以简单维护。时间复杂度 $O(n\log n)$。

另一个做法是，观察到一个长度 $l$ 会在第 $l$ 个字符加入后成为循环节，然后在之后某个时刻之后不再是循环节。离线所有操作，对每个长度二分是循环节的时间，然后差分统计答案。是否是循环节可以用哈希 $O(1)$ 判断。总时间复杂度同样为 $O(n\log n)$。