「BZOJ 2342」双倍回文-回文自动机

求一个回文串,使得这个回文串的一半也是回文串,输出其最长长度。

链接

BZOJ 2342

题解

先建出回文自动机,然后建出其 $fail$ 树,注意到 $fail$ 链指向的节点是这个节点的最长回文后缀。

建出的 $fail$ 树通过 $fail$ 链连接了所有本质不同的回文串,沿着 $fail$ 树走,就是从小的串往两边加字符形成的大的串。

所以我们可以从根节点开始 dfs,显然符合题意的回文串的长度必须是 $4$ 的倍数,对于当前节点,我们只需要判断其是否有长度为 $\frac {len} {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
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「BZOJ 2342」双倍回文 14-09-2017
* 回文自动机
* @author xehoth
*/
#include <bits/stdc++.h>
namespace IO {
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}
template <typename T>
inline void read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return;
c == '-' ? iosig = true : 0;
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig ? x = -x : 0;
}
inline void read(char &c) {
while (c = read(), isspace(c) && c != -1)
;
}
inline int read(char *buf) {
register int s = 0;
register char c;
while (c = read(), isspace(c) && c != -1)
;
if (c == -1) {
*buf = 0;
return -1;
}
do
buf[s++] = c;
while (c = read(), !isspace(c) && c != -1);
buf[s] = 0;
return s;
}
const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
x < 0 ? (print('-'), x = -x) : 0;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void print(const char *s) {
for (; *s; s++) print(*s);
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
struct InputOutputStream {
template <typename T>
inline InputOutputStream &operator>>(T &x) {
read(x);
return *this;
}
template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
~InputOutputStream() { flush(); }
} io;
}
namespace {
using IO::io;
const int MAX_SIGMA = 26;
const int MAXN = 500010;
const int SIGMA = 26;
struct Node {
int len, cnt, fail, c[MAX_SIGMA];
};
struct Graph {
typedef std::vector<int> Vector;
Vector edge[MAXN + 2];
inline void addEdge(const int u, const int v) { edge[u].push_back(v); }
inline Vector &operator[](const int i) { return edge[i]; }
};
struct PalindromicTree {
static const int even = 0;
static const int odd = 1;
Node d[MAXN + 1];
int cur, last, size;
char s[MAXN + 1];
PalindromicTree() {
d[odd].len = -1, d[even].fail = d[odd].fail = odd, s[size = 0] = -1;
cur = 2;
}
Graph g;
inline void extend(char c) {
s[++size] = c;
register int &p = last;
while (s[size - d[p].len - 1] != s[size]) p = d[p].fail;
if (!d[p].c[c]) {
register int np = cur++, k = d[p].fail;
d[np].len = d[p].len + 2;
while (s[size - d[k].len - 1] != s[size]) k = d[k].fail;
d[np].fail = d[k].c[c], d[p].c[c] = np;
g.addEdge(d[np].fail, np);
}
p = d[p].c[c], d[p].cnt++;
}
int ans, vis[MAXN + 1];
inline void dfs(const int u) {
if (d[u].len % 4 == 0 && vis[d[u].len / 2])
ans = std::max(ans, d[u].len);
vis[d[u].len]++;
for (register int i = 0; i < g[u].size(); i++) dfs(g[u][i]);
vis[d[u].len]--;
}
inline void solve() {
register int n;
io >> n;
static char buf[MAXN + 1];
io >> buf;
for (register int i = 0; i < n; i++) extend(buf[i] - 'a');
dfs(0);
io << ans;
}
} task;
}
int main() {
// freopen("sample/1.in", "r", stdin);
task.solve();
return 0;
}
分享到