「BZOJ 1396/2865」识别子串-后缀数组+单调队列

给定一个字符串 $S$,定义一个位置 $i$ 的识别子串为包含这个位置且在原串只出现一次的字符串,求每个位置的识别子串的长度。

链接

BZOJ 1396
BZOJ 2865

题解

似乎网上都是 SAM 的做法,不过讲道理这题后缀数组更优

先对于 $S$ 建出其后缀数组,考虑 $ht$ 数组上相邻的三个串 $i - 1, i, i + 1$,若我们固定左端点为 $i$,考虑以 $i$ 为起点的的串对答案的影响,举个例子,如:banana(下标从 $1$ 开始)

其后缀数组为

1
2
3
4
5
6
7
pos s
6 a
4 ana
2 anana
1 banana
5 na
3 nana

当 $pos = 2$,即 $i = 3$ 时,anan 是最小的识别子串,我们发现识别子串的长度至少是 $\max {ht[i], ht[i + 1]} + 1$(因为和其他的串是 rmq 关系,所以小于这个长度就会出现多次),存在一个分界点 $x$,在 $[i, x]$ 内的答案均为 $\max \{ht[i], ht[i + 1]\} + 1$,而在其之后为 $\max\limits_{j = x + 1} ^ n j - i + 1$。

对于后缀 $i$,令 $h[i] = i + \max \{ht[rk[i]], ht[rk[i] + 1]\}$,那么每个位置 $i$ 的答案就是 $\max \{j, h[i]\} - i + 1$,于是我们有了一个 $O(n ^ 2)$ 的 DP。

考虑优化,对于位置 $i, i’(i \lt i’)$,显然 $h[i] \lt h[i’]$,且当 $j$ 足够大的时候 $i$ 一定比 $i’$ 更优。而当 $j$ 比较小的时候如果 $i$ 更优,需要 $h[i] - i \lt h[i’] - i’$。因此我们可以维护一个 $i, h[i], h[i] - i$ 都递增的单调队列。

使用 SA-IS 算法求后缀数组,故时间复杂度 $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
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
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「BZOJ 1396」识别子串 19-12-2017
* 后缀数组 + 单调队列
* @author xehoth
*/
#include <bits/stdc++.h>
namespace {
const int OUT_LEN = 1 << 18 | 1;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
(oh == obuf + OUT_LEN) && (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf);
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[21], cnt;
if (x != 0) {
(x < 0) && (print('-'), x = -x);
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
} else {
print('0');
}
}
struct OutputStream {
~OutputStream() { fwrite(obuf, 1, oh - obuf, stdout); }
template <typename T>
inline OutputStream &operator<<(T x) {
print(x);
return *this;
}
} io;
const int MAXN = 100000 + 9;
inline bool islms(const int i, const bool *t) {
return i > 0 && t[i] && !t[i - 1];
}
template <typename T>
inline void sort(T s, int *sa, const int len, const int sz, const int sigma,
bool *t, int *b, int *cb, int *p) {
memset(b, 0, sizeof(int) * sigma);
memset(sa, -1, sizeof(int) * len);
for (register int i = 0; i < len; i++) b[s[i]]++;
cb[0] = b[0];
for (register int i = 1; i < sigma; i++) cb[i] = cb[i - 1] + b[i];
for (register int i = sz - 1; i >= 0; i--) sa[--cb[s[p[i]]]] = p[i];
for (register int i = 1; i < sigma; i++) cb[i] = cb[i - 1] + b[i - 1];
for (register int i = 0; i < len; i++)
if (sa[i] > 0 && !t[sa[i] - 1]) sa[cb[s[sa[i] - 1]]++] = sa[i] - 1;
cb[0] = b[0];
for (register int i = 1; i < sigma; i++) cb[i] = cb[i - 1] + b[i];
for (register int i = len - 1; i >= 0; i--)
if (sa[i] > 0 && t[sa[i] - 1]) sa[--cb[s[sa[i] - 1]]] = sa[i] - 1;
}
template <typename T>
inline void sais(T s, int *sa, const int len, bool *t, int *b, int *b1,
const int sigma) {
register int i, j, x, p = -1, cnt = 0, sz = 0, *cb = b + sigma;
for (t[len - 1] = 1, i = len - 2; i >= 0; i--)
t[i] = s[i] < s[i + 1] || (s[i] == s[i + 1] && t[i + 1]);
for (i = 1; i < len; i++)
if (t[i] && !t[i - 1]) b1[sz++] = i;
sort(s, sa, len, sz, sigma, t, b, cb, b1);
for (i = sz = 0; i < len; i++)
if (islms(sa[i], t)) sa[sz++] = sa[i];
for (i = sz; i < len; i++) sa[i] = -1;
for (i = 0; i < sz; i++) {
for (x = sa[i], j = 0; j < len; j++) {
if (p == -1 || s[x + j] != s[p + j] || t[x + j] != t[p + j]) {
p = x, cnt++;
break;
} else if (j > 0 && (islms(x + j, t) || islms(p + j, t))) {
break;
}
}
sa[sz + (x >>= 1)] = cnt - 1;
}
for (i = j = len - 1; i >= sz; i--)
if (sa[i] >= 0) sa[j--] = sa[i];
register int *s1 = sa + len - sz, *b2 = b1 + sz;
if (cnt < sz)
sais(s1, sa, sz, t + len, b, b1 + sz, cnt);
else
for (i = 0; i < sz; i++) sa[s1[i]] = i;
for (i = 0; i < sz; i++) b2[i] = b1[sa[i]];
sort(s, sa, len, sz, sigma, t, b, cb, b2);
}
template <typename T>
inline void getHeight(T s, const int n, int *sa, int *rk, int *ht) {
for (register int i = 1; i <= n; i++) rk[sa[i]] = i;
for (register int i = 0, j = 0, k = 0; i < n; ht[rk[i++]] = k)
for (k ? k-- : 0, j = sa[rk[i] - 1]; s[i + k] == s[j + k]; k++)
;
}
struct SuffixArray {
char s[MAXN];
int n, sa[MAXN], rk[MAXN], ht[MAXN];
bool t[MAXN << 1];
inline void build(const int sigma) {
s[n] = 0, sais(s, sa, n + 1, t, rk, ht, sigma);
rk[0] = ht[0] = 0, getHeight(s, n, sa, rk, ht);
}
} d;
std::pair<int, int> q[MAXN], *l = q + 1, *r = q;
inline int calc(const std::pair<int, int> *p, const int x) {
return std::max(p->second, x) - p->first + 1;
}
inline void solve() {
d.n = fread(d.s, 1, MAXN, stdin);
while (isspace(d.s[d.n - 1])) d.n--;
d.build(127);
for (register int i = 0, tmp; i < d.n; i++) {
tmp = i + std::max(d.ht[d.rk[i]], d.ht[d.rk[i] + 1]);
if (tmp < d.n) {
while (l <= r && tmp - i <= r->second - r->first) r--;
r++;
r->first = i, r->second = tmp;
}
while (l < r && calc(l + 1, i) <= calc(l, i)) l++;
io << calc(l, i) << '\n';
}
}
} // namespace
int main() {
#ifdef DBG
freopen("sample/1.in", "r", stdin);
#endif
solve();
return 0;
}
分享到