Manacher

马拉车算法可以在$O(n)$的时间内找出一个字符串内的所有回文串。

下面讨论当所有回文串长度都为奇数的情况。对于每个位置 $i = 0 \dots n - 1$ ，我们找出值 $d_1[i]$ 。这表示以位置 $i$ 为中心的长度为奇数的回文串个数。换个角度，该者也表示了以位置 $i$ 为中心的最长回文串的半径长度（半径长度 $d_1[i]$为从位置 $i$ 到回文串最右端位置包含的字符个数）。

举例来说，字符串 $s = \mathtt{abababc}$ 以 $s[3] = b$ 为中心有三个奇数长度的回文串，最长回文串半径为 $3$，也即 $d_1[3] = 3$：

$$a\ \overbrace{b\ a\ \underset{s_3}{b}\ a\ b}^{d_1[3]=3}\ c$$

因此关键思路是，如果以某个位置 $i$ 为中心，我们有一个长度为 $l$ 的回文串，那么我们有以 $i$ 为中心的长度为 $l - 2$，$l - 4$，等等的回文串。所以 $d_1[i]$数组已经足够表示字符串中所有奇数长度子回文串的信息。

朴素算法

朴素算法通过下述方式工作：对每个中心位置 $i$，在比较一对对应字符后，只要可能，该算法便尝试将答案加 $1$。 该算法是比较慢的：它只能在 $O(n^2)$ 的时间内计算答案。

vector<int> d1(n);
for (int i = 0; i < n; i++) {
    d1[i] = 1;
    while (0 <= i - d1[i] && i + d1[i] < n && s[i - d1[i]] == s[i + d1[i]]) {
    d1[i]++;
    }
}

Manacher 算法

为了快速计算所有奇数长度子回文串的情况，我们维护已找到的最靠右的子回文串的 边界 $[l, r]$（即具有最大 $r$ 值的回文串，其中 $l$ 和 $r$ 分别为该回文串左右边界的位置）。初始时，我们置 $l = 0$ 和 $r = -1$（ -1 需区别于倒序索引位置，这里可为任意负数，仅为了循环初始时方便）。

过程

现在假设我们要对下一个 $i$ 计算 $d_1[i]$，而之前所有 $d_1[]$ 中的值已计算完毕。我们将通过下列方式计算：

• 如果 $i$ 位于当前子回文串之外，即 $i > r$，那么我们调用朴素算法。

  因此我们将连续地增加 $d_1[i]$，同时在每一步中检查当前的子串 $[i - d_1[i] \dots i + d_1[i]]$（$d_1[i]$ 表示半径长度，下同）是否为一个回文串。如果我们找到了第一处对应字符不同，又或者碰到了 $s$ 的边界，则算法停止。在两种情况下我们均已计算完 $d_1[i]$。此后，需记得更新 $[l, r]$。

• 现在考虑 $i \le r$ 的情况。我们将尝试从已计算过的 $d_1[]$ 的值中获取一些信息。首先在子回文串 $[l, r]$ 中反转位置 $i$，即我们得到 $j = l + (r - i)$。现在来考察值 $d_1[j]$。因为位置 $j$ 同位置 $i$ 对称，我们 几乎总是可以保证 $d_1[i] \ge d_1[j]$。该想法的图示如下（可认为以 $j$ 为中心的回文串被「拷贝」至以 $i$ 为中心的位置上）：

  $$\ldots\ \overbrace{ s_l\ \ldots\ \underbrace{ s_{j-d_1[j]+1}\ \ldots\ s_j\ \ldots\ s_{j+d_1[j]-1} }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-d_1[j]+1}\ \ldots\ s_i\ \ldots\ s_{i+d_1[j]-1} }_\text{palindrome}\ \ldots\ s_r }^\text{palindrome}\ \ldots$$

  然而有一个 棘手的情况 需要被正确处理：当「内部」的回文串到达「外部」回文串的边界时，即 $j - d_1[j] + 1 \le l$（或者等价的说，$i + d_1[j] - 1 \ge r$）。因为在「外部」回文串范围以外的对称性没有保证，因此直接置 $d_1[i] = d_1[j]$ 将是不正确的：我们没有足够的信息来断言在位置 $i$ 的回文串具有同样的长度。

  实际上，为了正确处理这种情况，我们应该「截断」回文串的长度，即置 $d_1[i] = r - i$。

  该种情况的图示如下（以 $j$ 为中心的回文串已经被截断以落在「外部」回文串内）：

  $$\ldots\ \overbrace{ \underbrace{ s_l\ \ldots\ s_j\ \ldots\ s_{j+(j-l)} }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-(r-i)}\ \ldots\ s_i\ \ldots\ s_r }_\text{palindrome} }^\text{palindrome}\ \underbrace{ \ldots \ldots \ldots \ldots \ldots }_\text{try moving here}$$

  该图示显示出，尽管以 $j$ 为中心的回文串可能更长，以致于超出「外部」回文串，但在位置 $i$，我们只能利用其完全落在」外部」回文串内的部分。然而位置 $i$ 的答案可能比这个值更大，因此接下来我们将运行朴素算法来尝试将其扩展至「外部」回文串之外，也即标识为 "try moving here" 的区域。

  经过上述操作，我们已经找到了$d1[i]$可能的最小值。之后我们将继续运行朴素算法以尝试尽可能增加 $d_1[i]$ 的值。

最后，仍有必要提醒的是，我们应当记得在计算完每个 $d_1[i]$ 后更新值 $[l, r]$。

Manacher 算法的实现

为了计算 $d_1[]$，我们有以下代码：

vector<int> d1(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
  int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
  while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
    k++;
  }
  d1[i] = k--;
  if (i + k > r) {
    l = i - k;
    r = i + k;
  }
}

统一处理

以上方案仅考虑了回文串长度为奇数时的情况，但实际上可以通过一个技巧将偶数长度也归纳进来。

给定一个长度为 $n$ 的字符串 $s$，我们在其 $n + 1$ 个空中插入分隔符 $\#$，从而构造一个长度为 $2n + 1$ 的字符串 $s'$。举例来说，对于字符串 $s = \mathtt{abababc}$，其对应的 $s' = \mathtt{\#a\#b\#a\#b\#a\#b\#c\#}$。

对于字母间的 $\#$，其实际意义为 $s$ 中对应的「空」。而两端的 $\#$ 则是为了实现的方便。

注意到，在对 $s'$ 计算 $d_1^{'}[]$ 后，对于任意一个 $s$ 中以位置 $i$ 为中心的回文串，若其原长度为奇数，那么变换后的回文的中心依旧是 $s[i]$ ，而若其原长度为偶数，那么变换后其长度为奇数，并且以#为中心。这样我们就只要直接计算 $s'$ 中奇数长度回文串的贡献即可。

int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) k++;

同时注意到这段代码，当 $i=0 \ and\ k=1$ 时下标会溢出，我们习惯在 $s'$ 开头再加一个符号~，不影响结论正确性。

对于该处理过程，以下结论不难证明：

变换类型	i	i'	原对称中心	d[i]	原以i下标为中心的极大回文串的长度（可奇可偶）	现对称中心	d1'[i']	现对应极大回文串的长度（奇数）
回文串长度为奇数，仅填充#	i	2i+1	s[i]	m	2m-1	s'[2i+1]	2m	4m-1
回文串长度为偶数，仅填充#	i	2i+1	s[i]	m	2m	'#'	2m+1	4m+1
回文串长度为奇数，填充#且前面加~	i	2i+2	s[i]	m	2m-1	s'[2i+2]	2m	4m-1
回文串长度为偶数，填充#且前面加~	i	2i+2	s[i]	m	2m	'#'	2m+1	4m+1

模板

https://www.luogu.com.cn/problem/P3805

//#define LOCAL

#include<bits/stdc++.h>

#define int        long long
#define yes        cout<<"YES"<<'\n'
#define no         cout<<"NO"<<'\n'
#define print(x)   cout<<(x)<<'\n'
#define forn(i, n)  for(long long i=0; i<n; i++)

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-4;
const double PI = acos(-1);
const int MAXN = 1e5 + 29;
struct point {
    int left, right, w;
} tree[MAXN];
int n;
int fa[MAXN];
string s, str;
int d1[(int) 1.1e7 * 2 + 10];

void manacher(int odd_length = str.size()) {

    for (int i = 1, l = 0, r = -1; i < odd_length; i++) {
        int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
        while (0 <= i - k && i + k < odd_length && str[i - k] == str[i + k]) {
            k++;
        }
        d1[i] = k--;
        if (i + k > r) {
            l = i - k;
            r = i + k;
        }
    }
}

signed main() {
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    getline(cin, s);
    str.push_back(7);
    for (const auto &item: s) {
        str.push_back(6);
        str.push_back(item);
    }
    str.push_back(6);

    manacher();

    print(*max_element(d1, d1 + str.size()) - 1);
}

Reference

https://oi-wiki.org/string/manacher