manacher

## 前言 以下内容大多摘抄自 [董晓算法](https://space.bilibili.com/517494241)。 ## 用途 Manacher 算法可以在 $O(n)$ 的时间内求出一个字符串内以任意一个字符为中点的最大回文串长度。 ## 前置芝士 - 回文半径：以 $i$ 为中心的最长回 ......

读了徐安矣2023年集训队论文写的，对于差分性质和习题，我会在理解清楚之后再补充。本篇博客仅讨论前两种算法。 首先，马拉车和回文自动机都是处理回文串问题的。但在此之前，学习一些更加简单的回文算法。 小 trick：把给定串的两头和缝隙插入相同字符，且在边界处用不同字符标记，使得长度为偶数的回文串和长 ......

算法简介 Manacher 算法用于求解一串字符串中的最长回文子串的长度。 如：abab 的最长回文子串的长度为3。 时间复杂度 $ O(n) $ 实现原理 1.构造 回文串有两种情况： 情况1：abba，其对称轴在两字符中间 情况2：abcba，其对称轴在中间字符上 由于 Manacher 算法只 ......

P3805 manacher 算法 时间限制(普通/Java):500MS/3000MS 内存限制:512.00MB 返回题目 描述 给出一个只由小写英文字符 a,b,c,…y,z 组成的字符串 S ,求 S 中最长回文串的长度 。 字符串长度为 n。 输入 一行小写英文字符 a,b,c,⋯,y,z ......

简介 求出字符串的所有回文子串。 算法思想和流程 我们想找到每一个字符 $i$ 作为回文中心的时候，最长回文串的半径 $r_i$ 是什么。那么以 $i$ 为中心，$[0, r_i]$ 为半径，都是回文子串，$(r_i, +\inf)$ 为半径，都不是。考虑暴力算法对于每一个中心向外探测，时间复杂度 ......