$\large{\textrm{Description}}$
给定一个长度为 $n$ 的字符串。
要求在 $O(n)$ 的时间复杂度之内求出它的最长回文子串的长度。
$\large{\textrm{Solution}}$
首先将整个字符串中任意两个位置间插入字符 #
(左右两端也要加上不同字符防止越界)。
例如原先是
a b c b a
处理后变为
$ # a # b # c # b # a # %
这样处理使得原串中的任意回文串在后串中都表示为奇数长度串的形式,且都有一个中心点。
设 $p_i$ 表示为以 $i$ 为中心点的最大半径(右端点到中心点的串的长度,包括两端)。
从左向右扫描每一个 $i$ ,
-
已知 $i$ 之前的所有回文串中右端点最靠右的串的中心点 $m$ 以及右端点 $r$ 。
-
若 $i \leq r$ ,设初始 $p_i = p_{2m - i}$($2m-i$ 为 $i$ 在此串上的对称点);否则设初始 $p_i = 1$ 。
-
不断扩大边界,若 $s_{i - p_i} = s_{i+p_i}$ 成立,$p_i$ 加一。
-
判断 $i + p_i - 1$ 是否大于 $r$ ,更新 $m$ 和 $r$ 。
$\large{\textrm{Time complexity}}$
每一个点都被扫过一次,时间复杂度 $O(n)$ 。
$\large{\textrm{Code}}$
#include <bits/stdc++.h>
using namespace std;
const int N = 2e7 + 10;
int n;
char a[N], b[N];
int p[N];
void init() {
int k = 0;
b[k ++ ] = '$', b[k ++ ] = '#';
for (int i = 0; i < n; i ++ ) b[k ++ ] = a[i], b[k ++ ] = '#';
b[k ++ ] = '^';
n = k;
}
void manacher() {
int mr = 0, mid;
for (int i = 0; i < n; i ++ ) {
if (i < mr) p[i] = min(p[mid + mid - i], mr - i);
else p[i] = 1;
while (b[i - p[i]] == b[i + p[i]]) p[i] ++ ;
if (i + p[i] > mr) {
mr = i + p[i];
mid = i;
}
}
}
int main() {
scanf("%s", a);
n = strlen(a);
init();
manacher();
int res = 0;
for (int i = 0; i < n; i ++ ) res = max(res, p[i] - 1);
printf("%d", res);
return 0;
}