[CF1037H]后缀自动机+线段树合并

刚学后缀自动机,做一发练习题学习一下

题目大意

给定一个串 $s$ ,多组询问,每次询问一个串 $t$ 使得 $s$ 在 $[l,r]$ 中的某一个子串的字典序严格大于 $t$ 且字典序最小

思路

考虑答案一定是 $s$ 在 $[l,r]$ 中与 $t$ 的某一个前缀匹配加上一个字符 $c$

所以可以求出 $t$ 与 $s$ 在 $[l,r]$ 中最长的前缀匹配,这时应该从后往前考虑,贪心找到一个字符 $c$ 即为答案

可以发现在 $endpos$ 类中至少有一个元素在 $[l,r]$ 中的点一定有一个在 $[l,r]$ 中的匹配

所以用线段树来维护每一个点的 $endpos$ 类,对于每一个点进行线段树合并

之后只要贪心求解即可,如果没有可以转移的其它字符为无解

代码

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
/***************************************************************
File name: CF1037H.cpp
Author: ljfcnyali
Create time: 2019年11月25日 星期一 14时09分15秒
***************************************************************/
#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 pii pair<int, int>
#define ls(x) Tree[x].lson
#define rs(x) Tree[x].rson
typedef long long LL;

const int maxn = 2e5 + 10;

struct SAM { int Next[26], len, fa; } Trie[maxn << 2];
struct node { int lson, rson, sum; } Tree[maxn << 5];
int tot = 1, last = 1, ret, n, m, Root[maxn], Begin[maxn], Next[maxn], To[maxn], e;
vector<int> suf;
char s[maxn];

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

inline void PushUp(int root) { Tree[root].sum = Tree[ls(root)].sum + Tree[rs(root)].sum; }

inline void Modify(int &root, int l, int r, int pos)
{
if ( !root ) root = ++ ret;
if ( l == r ) { Tree[root].sum = 1; return ; }
int Mid = l + r >> 1;
if ( pos <= Mid ) Modify(ls(root), l, Mid, pos);
else Modify(rs(root), Mid + 1, r, pos);
PushUp(root);
}

inline int Merge(int x, int y, int l, int r)
{
if ( !x || !y ) return x + y;
int root = ++ ret;
if ( l == r ) { Tree[root].sum = Tree[x].sum + Tree[y].sum; return root; }
int Mid = l + r >> 1;
ls(root) = Merge(ls(x), ls(y), l, Mid);
rs(root) = Merge(rs(x), rs(y), Mid + 1, r);
PushUp(root);
return root;
}

inline int Query(int root, int l, int r, int L, int R)
{
if ( !root ) return 0;
if ( L <= l && r <= R ) return Tree[root].sum;
int Mid = l + r >> 1, ret = 0;
if ( L <= Mid ) ret += Query(ls(root), l, Mid, L, R);
if ( Mid < R ) ret += Query(rs(root), Mid + 1, r, L, R);
return ret;
}

inline void Extand(int c)
{
int cur = ++ tot;
Trie[cur].len = Trie[last].len + 1;
Modify(Root[cur], 1, n, Trie[cur].len);
int p = last; last = cur;
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;
else
{
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[cur].fa = Trie[q].fa = clone;
}
}

inline void DFS(int u)
{
for ( int i = Begin[u]; i; i = Next[i] )
{
int v = To[i];
DFS(v);
Root[u] = Merge(Root[u], Root[v], 1, n);
}
}

inline void Solve(int L, int R)
{
int p = 1, N = str(s + 1) + 1;
suf.clear(); suf.push_back(-1);
s[N] = 'a' - 1;
REP(i, 1, N)
{
suf.push_back(-1);
REP(j, s[i] - 'a' + 1, 25)
{
int v = Trie[p].Next[j];
if ( v && Query(Root[v], 1, n, L + i - 1, R) ) { suf[i] = j; break ; }
}
if ( i == N ) break ;
p = Trie[p].Next[s[i] - 'a'];
if ( !p || !Query(Root[p], 1, n, L + i - 1, R) ) break ;
}
while ( !suf.empty() && suf.back() == -1 ) suf.pop_back();
if ( suf.empty() ) { puts("-1"); return ; }
REP(i, 1, suf.size() - 2) printf("%c", s[i]);
printf("%c\n", suf.back() + 'a');
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%s", s + 1); n = str(s + 1);
REP(i, 1, n) Extand(s[i] - 'a');
REP(i, 2, tot) add(Trie[i].fa, i);
DFS(1);
scanf("%d", &m);
REP(i, 1, m)
{
int l, r; scanf("%d %d %s", &l, &r, s + 1);
Solve(l, r);
}
return 0;
}