「十二省联考 2019」字符串问题【后缀数组 + 线段树】

Time Limit: 6 Sec Memory Limit: 1024 MB

Description

给定一个字符串 SS,定义 S\lvert S \rvert 表示 SS 的长度,子串 S(L,R)S(L, R) 为由 SS 中从左往右数第 LL 个字符到第 RR 个字符连接形成的字符串。两个字符串 S,TS, T 相加 S+TS + T 表示在 SS 后紧挨着写下 TT 得到的长度为 S+T\lvert S \rvert + \lvert T \rvert 的字符串。

Tiffany\text{Tiffany} 将从中划分出 nan_a 个子串作为 A\text{A} 类串,第 ii 个为 Ai=S(lai,rai)A_i = S(la_i, ra_i)

类似地,Yazid\text{Yazid} 将划分出 nbn_b 个子串作为 B\text{B} 类串,第 ii 个为 bi=S(lbi,rbi)b_i = S(lb_i, rb_i)

给定 mmAB\text{AB} 类串之间的单向边。规定 A\text{A} 类串 AiA_iAjA_j 之间有单向边当且仅当存在一个 B\text{B} 类串,其为 AjA_j 的前缀,且与 AiA_i 有边相连。

求最长链的长度。如果长度为无限长,输出 1-1

Input

输入的第一行包含一个整数 TT 表示数据组数。接下来依次描述每组数据,对于每组数据:

  • 11 行一个只包含小写字母的字符串 SS
  • 22 行一个整数 nan_a,表示 A\text{A} 类串的数目。接下来 nan_a 行,每行 22 个用空格隔开的整数。
    • ii 行的两个数分别为 lai,raila_i, ra_i,描述第 iiA\text{A} 类串。
  • 接下来一行一个整数 nbn_b,表示 B\text{B} 类串的数目。接下来 nbn_b 行,每行 22 个用空格隔开的整数。
    • ii 行的两个数分别为 lbi,rbilb_i, rb_i,描述第 ii 个 B 类串。
  • 接下来一行一个整数 mm,表示边数。接下来 mm 行,每行 22 个用空格隔开的整数。
    • 每行的两个整数 x,yx, y,表示第 xxA\text{A} 类串和第 yyB\text{B} 类串之间有单向边。
    • 保证 1xna,1 \leqslant x \leqslant n_a, 1ynb1 \leqslant y \leqslant n_b。保证没有重边。

Output

依次输出每组数据的答案,对于每组数据:

  • 一行一个整数表示最长链的长度。如果可以是无限长,输出 −1。

Sample Input

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
3
abaaaba
2
4 7
1 3
1
3 4
1
2 1
abaaaba
2
4 7
1 3
1
7 7
1
2 1
abbaabbaab
4
1 5
4 7
6 9
8 10
3
1 6
10 10
4 6
5
1 2
1 3
2 1
3 3
4 1

Sample Output

1
2
3
7
-1
13

Hint

对于第 11 组数据,最长链为 abaaaba\underline{\text{abaaaba}}

对于第 22 组数据,存在无限长的链。

对于第 33 组数据,最长链为 abbaabbaaaabb\underline{\text{abbaabbaaaabb}}

Constraints

nan_a nbn_b 测试点 mm AiBj\lvert A_i \rvert \geqslant \lvert B_j \rvert
1000\leqslant 1000 1000\leqslant 1000 131 \sim 3 2×105\leqslant 2 \times 10^5 保证
=1= 1 2×105\leqslant 2 \times 10^5 44 =nb= n_b 保证
2×105\leqslant 2 \times 10^5 2×105\leqslant 2 \times 10^5 585 \sim 8 2×105\leqslant 2 \times 10^5 保证
2×105\leqslant 2 \times 10^5 2×105\leqslant 2 \times 10^5 9109 \sim 10 2×105\leqslant 2 \times 10^5 不保证

表格中的 AiBj\lvert A_i \rvert \geqslant \lvert B_j \rvert 指的是任意 B\text{B} 类串的长度不超过任意 A\text{A} 类串的长度。

对于所有数据,保证 T100,T \leqslant 100, S2×105S \leqslant 2 \times 10^5

温馨提示本题使用多组数据评测,请注意清空数组

Solution

n=Sn = \lvert S \rvert。考虑建图,首先保留原始的边,如果 BjB_jAiA_i 的前缀,就从 BjB_jAiA_i 连一条单向边。所有 AiA_i 的权值为 Ai\lvert A_i \rvert,求出最长链即可,有环就输出 1-1

算法一

暴力建图并拓扑排序,借助 Hash\text{Hash} 加速。

时间复杂度为 O(nanb+m)O(n_a n_b + m),期望得分 304030 \sim 40 分。

算法二

可以发现复杂度出在 ``如果 BjB_jAiA_i 的前缀"" 这一部分的连边。如果保证 AiBj\lvert A_i \rvert \geqslant \lvert B_j \rvert,那么这一条件就等价于:

lcp(S(lai,n),S(lbj,n))Bj\text{lcp} \big( S(la_i, n), S(lb_j, n) \big) \geqslant \lvert B_j \rvert

如果把所有的 A\text{A} 类串按照 S(la,n)S(la, n) 进行后缀排序,那么满足条件的 AiA_i 就是一段连续的区间了 ((即包含 BjB_j 所在位置的,height\text{height} 最小值不小于 Bj\lvert B_j \rvert 的极长区间))。直接连边无法承受,显然可以用线段树优化建图。

n,na,nbn, n_a, n_b 同阶,时间复杂度为 O(nlogn)O(n \log n),期望得分 8080 分。

算法三

如果不再满足 AiBj\lvert A_i \rvert \geqslant \lvert B_j \rvert,那么这一条件等价于:

lcp(S(lai,n),S(lbj,n))Bj, AiBj\text{lcp} \big ( S(la_i, n), S(lb_j, n) \big) \geqslant \lvert B_j \rvert, \ \color{red} { \lvert A_i \rvert \geqslant \lvert B_j \rvert }

相当于多了一维的限制,可以考虑用主席树代替线段树。

n,na,nbn, n_a, n_b 视作同阶,时间复杂度为 O(nlogn)O(n \log n),期望得分 100100 分。

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
#include <bits/stdc++.h>
#define mid (l + r >> 1)
using namespace std;

inline int read() {
int x = 0; char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x;
}

const int maxn = 200010, maxm = maxn * 20;
int T, n, na, nb, SZ, cnt, tot, rk[maxn], sa[maxn], ht[maxn], pos[maxn];
int m, sc[maxn], buc[maxn], st[18][maxn], ord[maxn], rt[maxn], tmp[maxn];
int p, mp[maxn], ls[maxm], rs[maxm], head[maxm], d[maxm], w[maxm];
long long f[maxm]; char s[maxn];
queue<int> q;
struct str { int id, l, len; } a[maxn], b[maxn];
struct edge { int to, nxt; } e[maxn * 50];
bool comp1(str a, str b) { return rk[a.l] < rk[b.l]; }
bool comp2(int x, int y) { return a[x].len > a[y].len; }

void radix_sort() {
for (int i = 1; i <= SZ; i++) buc[i] = 0;
for (int i = 1; i <= n; i++) buc[rk[i]]++;
for (int i = 1; i <= SZ; i++) buc[i] += buc[i - 1];
for (int i = n; i; i--) sa[buc[rk[sc[i]]]--] = sc[i];
}

void calc_sa() {
for (int i = 1; i <= n; i++) rk[i] = s[i] - 'a' + 1, sc[i] = i;
SZ = 26, radix_sort();
for (int k = 1; ; k <<= 1) {
int cnt = 0;
for (int i = 1; i <= k; i++) sc[++cnt] = n - k + i;
for (int i = 1; i <= n; i++) if (sa[i] > k) sc[++cnt] = sa[i] - k;
radix_sort(), swap(rk, sc), rk[sa[1]] = cnt = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (sc[sa[i - 1]] == sc[sa[i]] &&
sc[sa[i - 1] + k] == sc[sa[i] + k] ? cnt : ++cnt);
}
SZ = cnt; if (cnt == n) break;
}
for (int i = 1, j = 0; i <= n; i++) {
if (rk[i] == 1) { j = ht[rk[i]] = st[0][rk[i]] = 0; continue; }
j = max(0, j - 1);
while (s[sa[rk[i] - 1] + j] == s[i + j]) j++;
ht[rk[i]] = st[0][rk[i]] = j;
}
for (int i = 1; (1 << i) <= n; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
}

int lcp(int x, int y) {
if (x == y) return n - x + 1;
x = rk[x], y = rk[y];
if (x > y) swap(x, y); x++;
int k = log2(y - x + 1);
return min(st[k][x], st[k][y - (1 << k) + 1]);
}

void add_edge(int from, int to) {
e[++cnt] = (edge){to, head[from]};
head[from] = cnt, d[to]++;
}

int ins(int k2, int l, int r) {
int k1 = ++tot; ls[k1] = ls[k2], rs[k1] = rs[k2];
if (l == r) { pos[l] = k1, w[k1] = a[l].len; return k1; }
if (mid >= p) ls[k1] = ins(ls[k2], l, mid);
else rs[k1] = ins(rs[k2], mid + 1, r);
add_edge(k1, ls[k1]), add_edge(k1, rs[k1]); return k1;
}

void add(int k, int l, int r, int ql, int qr, int p) {
if (!k || ql > qr) return;
if (l >= ql && r <= qr) { add_edge(p, k); return; }
if (mid >= ql) add(ls[k], l, mid, ql, qr, p);
if (mid < qr) add(rs[k], mid + 1, r, ql, qr, p);
}

long long topo_sort() {
long long ans = 0; int cnt = 0;
for (int i = 1; i <= tot; i++) {
if (!d[i]) q.push(i);
}
while (!q.empty()) {
int v = q.front(); q.pop();
cnt++, ans = max(ans, f[v] += w[v]);
for (int i = head[v]; i; i = e[i].nxt) {
f[e[i].to] = max(f[e[i].to], f[v]);
if (!--d[e[i].to]) q.push(e[i].to);
}
}
return cnt < tot ? -1 : ans;
}

int main() {
T = read();
while (T--) {
memset(head, 0, sizeof(head)), memset(d, 0, sizeof(d));
memset(w, cnt = tot = 0, sizeof(w)), memset(f, 0, sizeof(f));
scanf("%s", s + 1), na = read();
n = strlen(s + 1), calc_sa();
for (int i = 1, l, r; i <= na; i++) {
l = read(), r = read(), a[i] = (str){i, l, r - l + 1};
}
sort(a + 1, a + na + 1, comp1);
for (int i = 1; i <= na; i++) {
tmp[a[i].id] = ord[i] = i;
}
sort(ord + 1, ord + na + 1, comp2);
for (int i = n, j = rt[n + 1] = 0; i; i--) {
for (rt[i] = rt[i + 1]; j < na && a[ord[j + 1]].len == i; ) {
p = ord[++j], rt[i] = ins(rt[i], 1, na);
}
}
nb = read();
for (int i = 1, lb, len; i <= nb; i++) {
lb = read(), len = read(), len = len - lb + 1;
int l = 1, r = upper_bound(a + 1, a + na + 1,
(str){0, lb, 0}, comp1) - a - 1, ans = r + 1, ql;
while (l <= r) {
if (lcp(a[mid].l, lb) >= len) r = (ans = mid) - 1;
else l = mid + 1;
}
ql = ans, l = lower_bound(a + 1, a + na + 1,
(str){0, lb, 0}, comp1) - a, r = na, ans = l - 1;
while (l <= r) {
if (lcp(a[mid].l, lb) >= len) l = (ans = mid) + 1;
else r = mid - 1;
}
w[tot + i] = 0, add(rt[len], 1, na, ql, ans, tot + i);
}
m = read();
for (int i = 1, x, y; i <= m; i++) {
x = read(), y = read(), add_edge(pos[tmp[x]], tot + y);
}
tot += nb, printf("%lld\n", topo_sort());
}
return 0;
}

References

  • 字符串问题 解题报告 by Yuzhong Wang