Manacher
stripe_python · · 算法·理论
问题 给定字符串
顺序扫描
- 若
l+r-i 对应回文串被[l,r] 包含,直接查表。 - 若
l+r-i 对应回文串超出[l,r] ,向外暴力扩展。
求出
void manacher() {
for (int i = 1, l = 1, r = 0; i <= n; i++) {
int k = i > r ? 1 : min(d[l+r-i], r-i+1);
while (i-k >= 1 && i+k <= n && s[i-k] == s[i+k]) k++;
d[i] = k--;
if (i+k > r) l = i-k, r = i+k;
}
}
上面的代码只能求奇回文串。偶回文串可以单独讨论,也可以将原串变为
后转化为奇回文情形。
定理 本质不同回文子串至多
更强的结论是,每加入一个