0%

「POI 2005」SZA-Template

先来观察答案的几个强性质。

首先答案肯定是原串的一个$\tt{border}$,也就是失配树上的一条链。

再进一步观察:比如说答案在原串出现的位置分别为$p_1, p_2, p_3… p_k$(不妨设其严格升序),那么一定有$\max (p_i - p_{i-1}) \leq length(ans)$。

你问我为什么?如果大于的话就接不上了啊…

然后我们发现,只要满足上面那两个条件,那这个串一定就是个合法串。于是我们把这套东西搬到失配树上:

  1. 这个串是n在树上的祖先
  2. 这个串在树上的子树里所有节点的max_gap $\leq$ 这个串结尾的下标

问题就变成了怎么维护max_gap.

你发现这个东西维护最靠右边的1,最靠左边的1,答案就可以用线段树合并做到$\mathcal{O(n log n)}$,但是发现空间有点爆炸。

于是发现,可选的串只在一条链上,所以可以先全加进去,然后再逐步删,就可以用线段树做到$\mathcal{O(n log n)}$时间,$\mathcal{O(n)}$空间了。

然后发现这根本不用线段树,因为是逐步删答案只会不断变大,双向链表就可以解决。所以复杂度是$O(n)$的。

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
#include <bits/stdc++.h>

#define test(...) fprintf(stderr, __VA_ARGS__)
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef unsigned int ui;
typedef vector <pair <int, int> > edges;

const int N = 500010;
int fail[N], n, pre[N], nxt[N], to[N];
char s[N];
vi g[N];
int max_gap, ans = 0x7fffffff;
void erase_point(int u) {
if (pre[u] && nxt[u]) max_gap = max(max_gap, nxt[u] - pre[u]);
pre[nxt[u]] = pre[u]; nxt[pre[u]] = nxt[u];
}
void del(int);
void dfs(int u) {
if (max_gap <= u) ans = min(ans, u);
erase_point(u);
for (int i = 0; i < (int)g[u].size(); ++i) {
int v = g[u][i];
if (v != to[u]) del(v);
}
if (to[u]) dfs(to[u]);
}
void del(int u) {
erase_point(u);
for (int i = 0; i < (int)g[u].size(); ++i) {
int v = g[u][i];
del(v);
}
}
void solve() {
scanf ("%s", s + 1);
n = strlen(s + 1);
fail[1] = 0;
for (int i = 2, j = 0; i <= n; ++i) {
while (j && s[j + 1] != s[i]) j = fail[j];
j += s[j + 1] == s[i];
fail[i] = j;
}
for (int i = 1; i <= n; ++i) pre[i] = i-1, nxt[i] = i+1;
nxt[0] = 1; pre[n + 1] = n;
max_gap = 1;
int p = n;
while (p) to[fail[p]] = p, p = fail[p];
for (int i = 1; i <= n; ++i) g[fail[i]].push_back(i);
dfs(0);
cout << ans << '\n';
}

int main() {
#ifdef LOCAL
freopen("sample.in", "r", stdin);
#endif
int tests = 1;
while (tests--) solve();
return 0;
}