Border 的四种求法 之 回滚莫队

· · 个人记录

将 @ Bobby_0105 的思路进行完善。

一）思路

如果已知字符串 s 和其 border 长度 L，另 c 为某个字符，则 s+c 的 border 长度 \le L+1 。

推论：字符串 s+t 的 border 长度 \le L+|t| 。

那么似乎增加字符维护 border 长度是可行的。

二）框架

考虑回滚莫队。

将询问挂到对应块上。

我们将右指针一直扫到 n，对左指针进行回滚。

如果 border 扩展失配了，暴力缩短并使用哈希 check 。

这样右指针的移动和维护就是均摊正确的了。

问题来了，左端点加入字符并维护是均摊的，而不断回滚会破坏均摊。

三）解决方案

令左端点所在块为 [a,b]，对于 i\in[a,b]，记录 p_i 表示对于当前右指针 r，s[i,r] 的 border 最长可能是多少。

这里这个“可能"是我们第一部分的结论带来的。

记 d_i=p_i-p_{i+1},D=\sum d_i 。

初始时 p_i=b-i,d_i=1,D=\sqrt{n} 。

每当右指针右移时，所有 p_i 都要 +1，但是 D 仅仅会增加 1 。

每当处理询问时，如果失配，前面的 p_i 都要 -1，D 减少 1 。

而 D 始终大于 -n 。

所以每个块的时间复杂度都是均摊线性的。

至此，border 的四种求法可以用回滚莫队离线解决。