Manacher学习笔记

1. 用途

给定一个串，求该串中最长回文子串的长度

2. 算法过程

2.1. 预处理

回文串分为两类，奇回文和偶回文，所以对称中点是不确定的，可能是字符也可能是两个字符之间的空隙

所以可以在任意两个字符和开头结尾加上同一个奇怪的字符，此时的回文中心就一定是一个字符

2.2. 算法主体

定义数组p[i]表示以i为回文中心的最长回文半径，不难发现，p[i]-1就是最长的长度，因为要除去一个多余的字符

显然，可以向外扩展，暴力去跑有多少点符合条件，时间复杂度\(O(n^2)\)

但是在这种情况下，很多子串被重复访问，导致很多无意义的运算，时间复杂度很高

考虑优化，定义mr表示经过的，最靠右的点，而mid表示这个点是由哪个对称中心转移的

显然，对于每一个i，其实并没有必要都去拓展，可以分为如下情况：

1. \(i<mr\)

因为\([mid-p_{mid},mr]\)是回文的，记i关于mid的对称点为j

根据对称的性质，显然存在，\([j-p_j,j+p_j]=[i-p_i,i+p_i]\)

但是，当\(i+p_i\)大于\(mr\)时，就不一定满足条件了，所以可以在\(i+p_j\)和\(mr\)中去一个min值，再暴力扩展

2. \(i\ge mr\)

因为已经不存在对称，所以直接暴力即可

因为mid和mr都是不断右移，所以时间复杂度线性

2.3. 例题

P3805 【模板】manacher

https://gxyzoj.com/d/gxyznoi/p/112

题目描述

给出一个只由小写英文字符 \(\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z\) 组成的字符串 \(S\) ,求 \(S\) 中最长回文串的长度 。

字符串长度为 \(n\)。

输入格式

一行小写英文字符 \(\texttt a,\texttt b,\texttt c,\cdots,\texttt y,\texttt z\) 组成的字符串 \(S\)。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

aaa

样例输出 #1

3

提示

\(1\le n\le 1.1\times 10^7\)。