题目地址：

https://www.acwing.com/problem/content/description/1526/

给定一个字符串，请你求出其中的最长回文子串的长度。例如，给定字符串Is PAT&TAP symmetric?，最长回文子串为s PAT&TAP s，其长度是$11$。

输入格式：
包含一个非空字符串。

输出格式：
输出一个整数，表示给定字符串的最长回文子串的长度。

数据范围：
给定字符串的长度不超过$1000$。

可以用后缀数组。设字符串为$s$，设$s$翻转后是$s^{\prime }$，构造一个新串，其为$s$后拼接一个未出现的特殊字符，再拼接$s^{\prime }$。不妨用$s$表示新串，设其长度为$n$，求其后缀数组、排名数组$rk$和高度数组$h$，设$lcp(i,j)$为排名第$i$和第$j$的后缀的最长公共前缀的长度。接下来可以枚举中心点了，对于长奇数的回文子串情形，设中心点的下标为$k$，则以$k$为中心的最长回文子串的长度为$lcp(rk[k],rk[n-k+1])\times 2-1$，枚举$k=1,2,...,n$，而$lcp$可以通过在高度数组上做RMQ来达到$O(1)$询问；对于长偶数的回文子串情形，设中心偏右一个字符的下标为$k$，则此种情况的最长回文子串长度为$lcp(rk[k],rk[n-k+2])\times 2$，枚举$k=2,3,...,n$。枚举所有情况后取最大即可。代码如下：

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int N = 2010, M = 15;
int n, m;
char s[N];
int sa[N], rk[N], y[N], c[N], he[N];
int f[N][M];

void get_sa() {
  for (int i = 1; i <= n; i++) c[rk[i] = s[i]]++;
  for (int i = 2; i <= m; i++) c[i] += c[i - 1];
  for (int i = n; i; i--) sa[c[rk[i]]--] = i;

  for (int k = 1;; k <<= 1) {
    int num = 0;
    for (int i = n - k + 1; i <= n; i++) y[++num] = i;
    for (int i = 1; i <= n; i++) if (sa[i] > k) y[++num] = sa[i] - k;
    for (int i = 1; i <= m; i++) c[i] = 0;
    for (int i = 1; i <= n; i++) c[rk[i]]++;
    for (int i = 2; i <= m; i++) c[i] += c[i - 1];
    for (int i = n; i; i--) sa[c[rk[y[i]]]--] = y[i];
    swap(rk, y);
    rk[sa[1]] = num = 1;
    for (int i = 2; i <= n; i++)
      rk[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? num : ++num;
    if (num == n) break;
    m = num;
  }
}

void get_height() {
  for (int i = 1, k = 0; i <= n; i++) {
    if (rk[i] == 1) continue;
    if (k) k--;
    int j = sa[rk[i] - 1];
    while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
    he[rk[i]] = k;
  }
}

// 预处理一下高度数组上的ST表
void init() {
  for (int i = 1; i <= n; i++) f[i][0] = he[i];
  for (int j = 1; j <= log2(n); j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

// 询问排名第l的后缀和排名第r的后缀的最长公共前缀长度
int query(int l, int r) {
  // 注意要保证l <= r
  if (l > r) swap(l, r);
  l++;
  int j = log2(r - l + 1);
  return min(f[l][j], f[r - (1 << j) + 1][j]);
}

int main() {
  cin.getline(s + 1, 1010);
  n = strlen(s + 1), m = 256;
  s[n + 1] = 1;
  for (int i = 1; i <= n; i++) s[n + 1 + i] = s[n - i + 1];
  n = n * 2 + 1;
  s[n + 1] = 0;

  get_sa();
  get_height();

  init();

  int res = 0;
  for (int i = 1; i <= n / 2; i++) {
    res = max(res, query(rk[i], rk[n - i + 1]) * 2 - 1);
    if (i > 1) res = max(res, query(rk[i], rk[n - i + 2]) * 2);
  }

  printf("%d\n", res);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

时空复杂度$O(n\log n)$。