Manacher.

Table of Contents

  1. Description
  2. Solution

Description

求一个字符串中最长的由两个回文串拼接的子串。

Solution

Manacher预处理回文半径，递推每个点作为左/右端点的最长回文子串，除了Manacher更新， 还有：

$r_i = max(r_i, r_{i+2}-2), l_i = max(l_{i-2} - 2)$.

然后枚举每个#更新答案就好了.

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int maxn = 1e+5 + 5;

int n;
char s[maxn], c[maxn << 1];
int l[maxn << 1], r[maxn << 1], ans;
int f[maxn << 1];

void manacher() {
  int mx = 0, id = 0;
  int ptr = 0;
  c[++ptr] = '#';
  for (int i = 1; i <= n; ++i) {
    c[++ptr] = s[i];
    c[++ptr] = '#';
  }
  for (int i = 1; i <= ptr; ++i) {
    if (mx > i) f[i] = min(f[2 * id - i], mx - i);
    else f[i] = 1;
    while (c[i + f[i]] == c[i - f[i]]) f[i]++;
    if (i + f[i] > mx) mx = i + f[i], id = i;
    r[i + f[i] - 1] = max(r[i + f[i] - 1], f[i] - 1);
    l[i - f[i] + 1] = max(l[i - f[i] + 1], f[i] - 1);
  }
  n = ptr;
}

int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  manacher();
  for (int i = 3; i <= n; i += 2) {
    l[i] = max(l[i], l[i - 2] - 2);
  }
  for (int i = n; i >= 1; i -= 2) {
    r[i] = max(r[i], r[i + 2] - 2);
  }
  for (int i = 1; i <= n; i += 2) 
    if (l[i] && r[i]) ans = max(ans, l[i] + r[i]);
  printf("%d\n", ans);
  return 0;
}