「2021CCPC华为云挑战赛」[HDU 7091] 重叠的子串

「题意」

给定长为 $n$ 的小写字符串 $s$,有 $m$ 个询问。每次给定 $l,r$,表示子串 $s[l,r]$。判断 $s$ 中是否存在两个或多个出现的有重叠部分的给定子串。

$\sum{n}\leq 6\times10^5,\sum{m}\leq 3\times 10^6$

「链接」

7091

「分析」

查询「是否存在两个或多个出现的有重叠部分的子串」是个经典问题,类似的有「查询有多少个本质不同的多次出现的有重叠部分的子串」。

具体来说,对于子串 $t$,若它对应的Rpos集合中,存在两项,它们的间距小于 $|t|$,即说明 $s$ 中有两个 $t$ 且存在重叠。

子串 $s[l,r]$ 应该属于叶子节点 $s[1,r]$ 的某个祖先节点,查询它可以在Fail树上倍增,用 $O(n\log{n})\sim O(\log{n})$ 的复杂度解决。

而每个节点对应的Rpos集合可以通过线段树合并的方式,自叶子节点向上传递信息,合并时维护Rpos中相距最近的两项的间距,复杂度 $O(n\log{n})$。

查询时,比较 $s[l,r]$ 对应的Fail树上的节点对应的线段树上的节点所维护的Rpos里间距最小的相邻两项的间距和 $r-l+1$ 即可得到答案。

复杂度 $O((n+q)\log{n})$。

标算给的是启发式合并,$O(n\log^2{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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
/*
* @date:
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fir first
#define sec second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
#define up(i, l, r) for (int i = l; i <= r; ++i)
#define dn(i, l, r) for (int i = l; i >= r; --i)
#define Trav(i, x) for (auto & i : x)
#define pb push_back
template<class T, class G> bool chkMax(T &x, G y) {
return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
return y < x ? x = y, 1 : 0;
}

const int MAXN = 1e5 + 5;

struct SegmentTree {
static const int N = ::MAXN * 40;
static const int INF = 1e9;
struct Node {
int ls, rs, lm, rm, val;
} A[N];
int tot;
int newNode() {
auto &a = A[tot];
a.ls = a.rs = 0;
a.lm = INF, a.rm = -INF;
a.val = INF;
return tot++;
}
void init() {
tot = 0;
newNode();
}
void pushUp(int rt) {
auto &x = A[rt], &ls = A[A[rt].ls], &rs = A[A[rt].rs];
chkMin(x.lm, min(ls.lm, rs.lm));
chkMax(x.rm, max(ls.rm, rs.rm));
chkMin(x.val, min(ls.val, rs.val));
chkMin(x.val, rs.lm - ls.rm);
}
void update(int &rt, int l, int r, int p) {
if (!rt) rt = newNode();
if (l == r) {
A[rt].lm = A[rt].rm = p;
return ;
}
int m = (l + r) >> 1;
if (p <= m) update(A[rt].ls, l, m, p);
else update(A[rt].rs, m + 1, r, p);
pushUp(rt);
}
int merge(int u, int v, int l, int r) {
if (!u || !v) return u + v;
int x = newNode();
if (l == r) {
A[x].lm = A[x].rm = l;
return x;
}
int m = (l + r) >> 1;
A[x].ls = merge(A[u].ls, A[v].ls, l, m);
A[x].rs = merge(A[u].rs, A[v].rs, m + 1, r);
pushUp(x);
return x;
}
} T;

struct SuffixAutomaton {
static const int N = ::MAXN << 1;
static const int M = 26;
static const int LOG = 23;
struct Node {
int len, ch[M], fail;
} A[N];
int rt, tot, lst, n;
int Rpos[N], Rt[N], Pos[N];
int newNode() {
auto &a = A[tot];
a.len = a.fail = 0;
memset(a.ch, 0, sizeof a.ch);
return tot++;
}
void push_back(int c) {
int cur = newNode(), p = lst;
A[cur].len = A[p].len + 1;
Rpos[cur] = A[cur].len;
Pos[Rpos[cur]] = cur;
T.update(Rt[cur], 1, n, Rpos[cur]);
for (; p && !A[p].ch[c]; p = A[p].fail) A[p].ch[c] = cur;
if (!p) {
A[cur].fail = rt;
} else {
int q = A[p].ch[c];
if (A[q].len == A[p].len + 1) {
A[cur].fail = q;
} else {
int clone = newNode();
A[clone] = A[q];
A[clone].len = A[p].len + 1;
A[cur].fail = A[q].fail = clone;
Rpos[clone] = Rpos[q];
for (; p && A[p].ch[c] == q; p = A[p].fail) A[p].ch[c] = clone;
}
}
lst = cur;
}
int Fa[N][LOG];
void sort() {
static int a[N], b[N];
memset(a, 0, sizeof a);
for (int i = 1; i < tot; ++i) ++a[A[i].len];
for (int i = 1; i <= n; ++i) a[i] += a[i - 1];
for (int i = tot - 1; i >= 1; --i) b[a[A[i].len]--] = i;
for (int i = tot - 1; i >= 1; --i) {
Rt[A[b[i]].fail] = T.merge(Rt[b[i]], Rt[A[b[i]].fail], 1, n);
}
for (int i = 1; i < tot; ++i) Fa[i][0] = A[i].fail;
for (int j = 1; j < LOG; ++j) {
for (int i = 1; i < tot; ++i) {
Fa[i][j] = Fa[Fa[i][j - 1]][j - 1];
}
}
}
void build(char s[]) {
tot = 1;
rt = lst = newNode();
memset(Rt, 0, sizeof Rt);
T.init();
n = strlen(s);
for (int i = 0; i < n; ++i) push_back(s[i] - 'a');
sort();
}
void solve(int l, int r) {
int p = Pos[r], len = r - l + 1;
for (int i = LOG - 1; i >= 0; --i) {
if (A[Fa[p][i]].len >= len) p = Fa[p][i];
}
if (T.A[Rt[p]].val < len) puts("Yes");
else puts("No");
}
} sam;

int n, m;
char s[MAXN];

void solve() {
scanf("%d%d%s", &n, &m, s);
sam.build(s);
for (int i = 1, l, r; i <= m; ++i) {
scanf("%d%d", &l, &r);
sam.solve(l, r);
}
}

int main() {
int Case;
scanf("%d", &Case);
while (Case--) solve();
return 0;
}