知识

如何正确使用马拉车 (manacher)

manacher 算法是用来求最长回文串长度的算法,复杂度是线性的($O(n)$) 基本思想是枚举以每一个点为中心,找出可以扩展的最长长度(用 r[i] 表示),然而会出现长度为偶数的情况无法枚举到的情况,所以首先要把字符串预处理一下。 (更多…)

hawa130