Manacher 算法用于在 $O(n)$ 时间内寻找字符串中的最长回文子串。通过对原串进行预处理和巧妙的“镜像”思路，它将暴力中心扩展的最坏 $O(n^2)$ 降至线性。
考虑回文串的定义：
- 空串是回文串。
- 长度为 1 的串是回文串。
- 如果 $A$ 是回文串，$a$ 是一个字符，则 $a A a$ 是回文串。
也就是说：如果一个串是回文串，则它去掉开头和结尾的字符后亦然。这意味着一个回文子串包含着更小的回文子串。
考虑设 $\mathrm{p}_i$ 表示以 $i$ 为中心的最长回文子串长度是多少（或言：$\left[i-\operatorname{p}_i+1, i+\operatorname{p}_i-1\right]$ 是极长回文串）。
考虑回文串自带一个对称结构，维护当前所有回文串中右端点最靠右的回文串是谁，记它为（$m, \operatorname{r}$）。现在枚举到一个位置 $i$ ，考虑：
- 当 $i>\operatorname{r}$ 的时候，直接暴力判断 $i$ 最远能向两边延申多长的回文串，然后用其更新 $r$。
- 当 $i \leq \operatorname{r}$ 的时候，说明以 $m$ 为中心，$i$ 存在一个对称点 $j=m-(i-m)$ 。容易见到 $\operatorname{len}_i \geq \min \left(\operatorname{r}-i+1, \operatorname{p}_j\right)$，因此可以直接取后再暴力更新。
这么做的复杂度当然是暴力更新的次数。然而每次暴力更新一定都会使得 maxr 变大，因此总复杂度线性。
例题
P3805 【模板】manacher
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
#define fir first
#define sec second
#define ep emplace
#define eb emplace_back
#define lowbit(x) ((x) & (-(x)))
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * f;
}
const int N = 22000010;
int n, m, ans, p[N];
char s[N], t[N];
int main() {
scanf("%s", s + 1);
n = strlen(s + 1), t[0] = '~';
for (int i = 1; i <= n; i ++ ) t[ ++ m] = '#', t[ ++ m] = s[i];
t[ ++ m] = '#';
for (int i = 1, r = 0, mid = 0; i <= m; i ++ ) {
if (i <= r) p[i] = min(p[mid * 2 - i], r - i + 1);
while (t[i - p[i]] == t[i + p[i]]) p[i] ++ ;
if (i + p[i] > r) r = i + p[i] - 1, mid = i;
ans = max(ans, p[i] - 1);
}
printf("%d\n", ans);
return 0;
}P4555 [国家集训队] 最长双回文串
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
#define fir first
#define sec second
#define ep emplace
#define eb emplace_back
#define lowbit(x) ((x) & (-(x)))
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * f;
}
const int N = 400010;
int n, m, ans, p[N], L[N], R[N];
char s[N], t[N];
int main() {
scanf("%s", s + 1);
n = strlen(s + 1), t[0] = '~';
for (int i = 1; i <= n; i ++ ) t[ ++ m] = '#', t[ ++ m] = s[i];
t[ ++ m] = '#';
for (int i = 1; i <= n; i ++ ) L[i] = R[i] = 1;
for (int i = 1, r = 0, mid = 0; i <= m; i ++ ) {
if (i <= r) p[i] = min(p[mid * 2 - i], r - i + 1);
for (; t[i - p[i]] == t[i + p[i]]; p[i] ++ );
if (i + p[i] > r) r = i + p[i] - 1, mid = i;
R[i + p[i] - 1] = max(R[i + p[i] - 1], p[i] - 1);
L[i - p[i] + 1] = max(L[i - p[i] + 1], p[i] - 1);
}
for (int i = m; i >= 1; i -= 2) R[i] = max(R[i], R[i + 2] - 2);
for (int i = 1; i <= m; i += 2) L[i] = max(L[i], L[i - 2] - 2);
for (int i = 3; i < m; i += 2) ans = max(ans, R[i] + L[i]);
printf("%d\n", ans);
return 0;
}P4287 [SHOI2011] 双倍回文
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
#define fir first
#define sec second
#define ep emplace
#define eb emplace_back
#define lowbit(x) ((x) & (-(x)))
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * f;
}
const int N = 1000010;
int n, m, p[N];
char s[N], t[N << 1];
priority_queue<PII, vector<PII>, greater<PII>> q;
set<int> st;
int main() {
n = read();
scanf("%s", s + 1), t[0] = '!';
for (int i = 1; i <= n; i ++ ) t[ ++ m] = '#', t[ ++ m] = s[i];
t[ ++ m] = '#';
for (int i = 1, r = 0, mid = 0; i <= m; i ++ ) {
if (i <= r) p[i] = min(p[2 * mid - i], r - i + 1);
for (; t[i - p[i]] == t[i + p[i]]; p[i] ++ );
if (i + p[i] > r) r = i + p[i] - 1, mid = i;
}
int ans = 0;
for (int r = 1; r <= m; r += 2) {
q.ep(r + p[r] - 1, r), st.ep(r);
while (q.size() && q.top().fir < r) st.erase(q.top().sec), q.pop();
int l = r - p[r] + 1, mid = (l + r) >> 1;
auto it = st.lower_bound(mid);
if (it != st.end()) ans = max(ans, (r - *it) << 1);
}
printf("%d\n", ans);
return 0;
}