[十二省联考2019字符串问题]后缀自动机+线段树优化建边

思路

首先考虑题目限制,即 \(A_x\) 若支配 \(B_y\)\(A_x\) 下一个为 \(A_z\) 当且仅当 \(B_y\)\(A_z\) 前缀

看到这种子串,首先莽一个 \(SAM\) 出来,然后发现没有想 \(pitch\)

如果莽了一个 \(SAM\) ,如果是前缀的话没有怎么利用 \(SAM\) 的性质,所以考虑把原串反转,这样限制条件变为了 \(B_y\)\(A_z\) 后缀,也就是 \(B_y\)\(SAM\) 上的点 \(b_y\)\(A_z\)\(SAM\) 上的点 \(a_z\)\(fail\) 树祖先(包括本身)

注意,这一部分有一个小小的 \(pitch\) ,但我们在后文再讨论

  • 查找一个字符串在 \(SAM\) 上的点

    该操作为 \(SAM\) 套路操作,具体为建 \(fail\) 树然后树上倍增找祖先

    对于一个字符串 \([l,r]\) ,从其前缀 \([1,r]\) 所在的点开始倍增,如果第 \(2^j\) 祖先的 \(Trie_i.len\) 大于等于当前串的长度,则往上跳 \(2^j\)

  • \(DAG\) 上求最长路

    如果我们建出来了一个图,如果该图有环很明显答案是 \(-1\),则该图一定是一个 \(DAG\)

    对于 \(DAG\) 上求最长路可以拓扑排序然后扫一遍即可,判是否有环同理

  • 线段树优化建边

    观察我们的连边,很明显是从 \(SAM\) 上一个点连向 \(fail\) 树上一整个子树

    所以可以将 \(fail\) 树按照 \(DFS\) 序重新编号,那么一整棵子树的编号就是连续的

    接下来考虑线段树优化建边,我们可以将 \(fail\) 树上所有点用一个类似与线段树的结构重新连边,边权均为 \(0\) ,(即父亲向两个儿子各连一个边权为 \(0\) 的单向边),然后每次从一个点向另外一个区间连边就只需要在这棵线段树上找到 \(log_2n\) 个区间连边即可

    注意,我们这种建边保证了不会出现 \(0\) 环,所以满足我们对 \(DAG\) 的限制

  • 发现我们无法通过 \(|A_i|<|B_j|\) 的测试点,很明显我们想了一些 \(pitch\) (呼应前文)

    这是因为如果有一个 \(A\) 类串和一个 \(B\) 类串同时出现在一个 \(SAM\) 节点上,且 \(|A_i|<|B_j|\) ,那么这个时候的 \(B_j\) 是不能连向 \(A_i\) 的,这不满足我们题意,但是我们建边时产生了这样一条边

    所以需要建完 \(SAM\) 后进行拆点,把所有这样的点按照 \(len\) 拆开,具体实现可以使用 \(set\) ,注意细节即

综上,我们使用极其简单的方法写完了这题

代码

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
/***************************************************************
File name: P5284.cpp
Author: ljfcnyali
Create time: 2020年06月04日 星期四 16时12分31秒
***************************************************************/
#include<bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for ( int i = (a), _end_ = (b); i <= _end_; ++ i )
#define mem(a) memset ( (a), 0, sizeof ( a ) )
#define str(a) strlen ( a )
#define int long long
#define pii pair<int, int>
#define x first
#define y second
#define lson root << 1
#define rson root << 1 | 1
typedef long long LL;

const int maxn = 2e6 + 10;
const int maxm = 5e6;

int T, n, N, m1, m2, m, tot, last, Begin[maxm], Next[maxm], To[maxm], e, ans, W[maxm], id[maxm], cnt;
int anc[maxn][20], f[maxn], a[maxn], b[maxn], dis[maxm], val[maxm], dfn[maxm], size[maxm], deg[maxm];
set<int> Edge[maxn];
set<tuple<int, int, int > > Set[maxn];
struct node { int Next[26], len, fa; } Trie[maxn];
char s[maxn];

inline void add(int u, int v, int w) { ++ deg[v]; To[++ e] = v; Next[e] = Begin[u]; Begin[u] = e; W[e] = w; }

inline void Build(int root, int l, int r)
{
if ( l == r ) { id[l] = root; return ; }
int Mid = l + r >> 1;
Build(lson, l, Mid); Build(rson, Mid + 1, r);
add(root, lson, 0); add(root, rson, 0);
}

inline void Modify(int root, int l, int r, int L, int R, int x, int val)
{
if ( L <= l && r <= R ) { add(x, root, val); return ; }
int Mid = l + r >> 1;
if ( L <= Mid ) Modify(lson, l, Mid, L, R, x, val);
if ( Mid < R ) Modify(rson, Mid + 1, r, L, R, x, val);
}

inline void Extand(int c)
{
int p = last, cur = ++ tot; last = tot; Trie[cur].len = Trie[p].len + 1;
while ( p && !Trie[p].Next[c] ) { Trie[p].Next[c] = cur; p = Trie[p].fa; }
if ( !p ) { Trie[cur].fa = 1; return ; }
int q = Trie[p].Next[c];
if ( Trie[p].len + 1 == Trie[q].len ) { Trie[cur].fa = q; return ; }
int clone = ++ tot;
Trie[clone] = Trie[q]; Trie[clone].len = Trie[p].len + 1;
while ( p && Trie[p].Next[c] == q ) { Trie[p].Next[c] = clone; p = Trie[p].fa; }
Trie[q].fa = Trie[cur].fa = clone;
}

inline void DFS(int u)
{
dfn[u] = ++ cnt; size[u] = 1;
for ( auto v : Edge[u] ) { DFS(v); size[u] += size[v]; }
}

inline int Get(int pos, int len)
{
int p = f[pos];
for ( int j = 18; j >= 0; -- j ) if ( Trie[anc[p][j]].len >= len ) p = anc[p][j];
return p;
}

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

signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%lld", &T);
memset(dis, -1, sizeof(dis));
while ( T -- )
{
scanf("%s", s + 1); n = str(s + 1); reverse(s + 1, s + n + 1);
// cerr << endl;
// cerr << N << endl;
REP(i, 1, N / 4)
{
Trie[i].len = Trie[i].fa = 0;
REP(j, 0, 25) Trie[i].Next[j] = 0;
Edge[i].clear(); Set[i].clear();
}
REP(i, 0, N)
{
Begin[i] = deg[i] = 0; dis[i] = -1;
}
e = cnt = 0; tot = last = 1;
REP(i, 1, n) { Extand(s[i] - 'a'); f[i] = last; }
N = tot;
REP(i, 1, N) { anc[i][0] = Trie[i].fa; Edge[Trie[i].fa].insert(i); }
REP(j, 1, 18) REP(i, 1, N) anc[i][j] = anc[anc[i][j - 1]][j - 1];

read(m1);
REP(i, 1, m1)
{
int x, y; read(x); read(y);
a[i] = Get(n - x + 1, y - x + 1); val[i] = y - x + 1;
Set[a[i]].insert(make_tuple(val[i], 1, i));
}
read(m2);
REP(i, 1, m2)
{
int x, y; read(x); read(y);
b[i] = Get(n - x + 1, y - x + 1);
Set[b[i]].insert(make_tuple(y - x + 1, 2, i));
}
// cerr << N << endl;
REP(i, 1, N)
for ( auto it = Set[i].begin(); it != Set[i].end(); ++ it )
{
if ( get<0>(*it) == Trie[anc[i][0]].len )
{
if ( get<1>(*it) == 1 ) a[get<2>(*it)] = anc[i][0];
else b[get<2>(*it)] = anc[i][0];
continue ;
}
if ( get<0>(*it) == Trie[i].len ) continue ;
++ N; Edge[anc[i][0]].erase(i); Edge[anc[i][0]].insert(N);
Edge[N].insert(i); anc[i][0] = N; Trie[N].len = get<0>(*it);
if ( get<1>(*it) == 1 ) a[get<2>(*it)] = anc[i][0];
else b[get<2>(*it)] = anc[i][0];
}

DFS(1); Build(1, 1, N);

read(m);
REP(i, 1, m)
{
int x, y; read(x); read(y);
Modify(1, 1, N, dfn[b[y]], dfn[b[y]] + size[b[y]] - 1, id[dfn[a[x]]], val[x]);
}
REP(i, 1, m1) Modify(1, 1, N, dfn[a[i]], dfn[a[i]], id[1], 0);
// cerr << N << endl;

N *= 4;
queue<int> Q; REP(i, 1, N) if ( !deg[i] ) { dis[i] = 0; Q.push(i); }
while ( !Q.empty() )
{
int u = Q.front(); Q.pop();
for ( int i = Begin[u]; i; i = Next[i] )
{
int v = To[i]; -- deg[v];
dis[v] = max(dis[v], dis[u] + W[i]);
if ( !deg[v] ) Q.push(v);
}
}
REP(i, 1, N) if ( deg[i] > 0 ) { puts("-1"); goto Next; }

ans = 0;
REP(i, 1, m1) ans = max(ans, dis[id[dfn[a[i]]]] + val[i]);
printf("%lld\n", ans);
Next : ;
}
return 0;
}