又是一道(SAM)维护(endpos)集合的题，我直接把CF700E的板子粘过来了QwQ
思路
如果我们有([l,r])对应的(SAM)，只需要在上面贪心就可以了。因为要求的是字典序比(T)大且最小的子串，我们从前到后让尽可能多的位相等，如果再也无法相等了就从后往前找一位变大。
但是每次询问会给我们一个可行区间([l,r])，而我们又显然不能直接把对应区间的(SAM)建出来，否则复杂度会(GG)。
仔细想一下，其实我们并不需要知道([l,r])区间对应的(SAM)，只要知道能否向某一个结点转移就行了。这个我们可以用(endpos)集合来判断。具体一下，就是当前已经考虑了(i)个字符且在结点(u)，现在需要判断能否转移到(v)，只需要判断(u)是否有到(v)的转移边和(v)结点的(endpos)是否有元素在([l+i-1,r])中就行了
(endpos)拿线段树合并维护一下就行了（也可以用树上主席树搞一下）
其实本菜鸡来学这个套路完全是为写你的名字做铺垫的
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define IINF 0x3f3f3f3f3f3f3f3fLL
#define ull unsigned long long
#define pii pair<int, int>
#define uint unsigned int
#define mii map<int, int>
#define lbd lower_bound
#define ubd upper_bound
#define INF 0x3f3f3f3f
#define vi vector<int>
#define ll long long
#define mp make_pair
#define pb push_back
#define N 200000
#define Q 200000
int n, q, m;
char s[N+5], t[N+5], ans[N+5];
struct SAM {
int nxt[26][2*N+5], maxlen[2*N+5], link[2*N+5], tot, lst;
int sumv[100*N+5], ch[2][100*N+5], root[2*N+5], nid;
int node[N+5];
vi G[2*N+5];
void init() {
tot = lst = 1;
nid = 0;
}
void pushup(int o) {
sumv[o] = sumv[ch[0][o]]+sumv[ch[1][o]];
}
void add(int &o, int l, int r, int x) {
if(!o) o = ++nid;
if(l == r) {
sumv[o] = 1;
return ;
}
int mid = (l+r)>>1;
if(x <= mid) add(ch[0][o], l, mid, x);
else add(ch[1][o], mid+1, r, x);
pushup(o);
}
int merge(int o, int u, int l, int r) {
if(!o || !u) return o|u;
int v = ++nid;
if(l == r) {
sumv[v] = sumv[o]+sumv[u] ? 1 : 0;
return v;
}
int mid = (l+r)>>1;
ch[0][v] = merge(ch[0][o], ch[0][u], l, mid);
ch[1][v] = merge(ch[1][o], ch[1][u], mid+1, r);
pushup(v);
return v;
}
int query(int o, int l, int r, int L, int R) {
if(L > R || !o) return 0;
if(L <= l && r <= R) return sumv[o];
int ret = 0, mid = (l+r)>>1;
if(L <= mid) ret += query(ch[0][o], l, mid, L, R);
if(R > mid) ret += query(ch[1][o], mid+1, r, L, R);
return ret;
}
void extend(int c) {
int cur = ++tot;
maxlen[cur] = maxlen[lst]+1;
while(lst && !nxt[c][lst]) nxt[c][lst] = cur, lst = link[lst];
if(!lst) link[cur] = 1;
else {
int p = lst, q = nxt[c][p];
if(maxlen[q] == maxlen[p]+1) link[cur] = q;
else {
int clone = ++tot;
maxlen[clone] = maxlen[p]+1;
link[clone] = link[q], link[q] = link[cur] = clone;
for(int i = 0; i < 26; ++i) nxt[i][clone] = nxt[i][q];
while(p && nxt[c][p] == q) nxt[c][p] = clone, p = link[p];
}
}
lst = cur;
}
void dfs(int u) {
for(int i = 0, v; i < G[u].size(); ++i) {
v = G[u][i];
dfs(v);
root[u] = merge(root[u], root[v], 1, n);
}
}
void build() {
init();
for(int i = 1; i <= n; ++i) {
add(root[tot+1], 1, n, i);
extend(s[i]-'a');
}
for(int i = 2; i <= tot; ++i) G[link[i]].pb(i);
dfs(1);
}
void search(int L, int R) {
m = strlen(t+1);
int u = 1, v, x;
for(int i = 1; 1; ++i) {
ans[i] = -1;
for(int j = max(t[i]-'a'+1, 0); j < 26; ++j) {
v = nxt[j][u];
if(v && query(root[v], 1, n, L+i-1, R)) {
ans[i] = j;
break;
}
}
v = nxt[max(t[i]-'a', 0)][u];
x = i;
if(i == m+1 || !v || !query(root[v], 1, n, L+i-1, R)) break;
u = v;
}
while(x && ans[x] == -1) --x;
if(!x) printf("-1
");
else {
for(int j = 1; j < x; ++j) printf("%c", t[j]);
printf("%c
", ans[x]+'a');
}
}
}sam;
int main() {
scanf("%s%d", s+1, &q);
n = strlen(s+1);
sam.build();
for(int i = 1, L, R; i <= q; ++i) {
scanf("%d%d%s", &L, &R, t+1);
sam.search(L, R);
}
return 0;
}