题目
题目大意
给定一个字符串$S$，每次询问给定$l,r$和一个字符串$T$，查询$S[l…r]$中字典序大于$T$的最小的子串，如果没有输出$-1$
Examples
input
baa
5
1 2 ba
2 3 a
1 2 b
2 3 aa
1 3 b
output
-1
aa
ba
-1
ba
input
bacb
4
1 2 ba
2 3 ac
1 3 ac
3 4 c
output
-1
c
b
cb
input
bba
1
1 1 b
output
-1
题解
建好$S$串的$SAM$直接用$T$串在上面递归跑就行，枚举$26$个字符判断一下哪个符合条件，回溯的时候记录答案，至于查询$[l,r]$，用线段树合并一下维护即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl s[k].l
# define tr s[k].r
# define mid (l+r>>1)
using namespace std;
const int MAX=2e5+5;
struct p{
int l,r;
}s[MAX<<5];
int n,tot,Q,__L;
int rt[MAX];
char a[MAX],b[MAX];
bool Fl;
void change(int l,int r,int &k,int x)
{
if(!k) k=++tot;
if(l==r) return;
if(x<=mid) change(l,mid,tl,x);
else change(mid+1,r,tr,x);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
int k=++tot;
return tl=merge(s[x].l,s[y].l),tr=merge(s[x].r,s[y].r),k;
}
bool ask(int l,int r,int k,int L,int R)
{
if(r<L||R<l||!k) return 0;
if(l>=L&&r<=R) return 1;
return (ask(l,mid,tl,L,R)|ask(mid+1,r,tr,L,R));
}
struct SAM{
int l,r,L;
int len[MAX],fa[MAX],tax[MAX],id[MAX];
int son[MAX][26];
SAM() {l=r=1;}
void ins(int x,int id)
{
int tt=r;
len[r=++l]=++L,change(1,n,rt[r],id);
for(;tt&&!son[tt][x];tt=fa[tt])
son[tt][x]=r;
if(!tt) return void(fa[r]=1);
int qwq=son[tt][x];
if(len[qwq]==len[tt]+1) return void(fa[r]=qwq);
len[++l]=len[tt]+1,fa[l]=fa[qwq],fa[qwq]=fa[r]=l;
for(int i=0;i<26;++i)
son[l][i]=son[qwq][i];
for(int i=tt;son[i][x]==qwq;i=fa[i])
son[i][x]=l;
}
void Init()
{
for(int i=1;i<=l;++i)
++tax[len[i]];
for(int i=1;i<=n;++i)
tax[i]+=tax[i-1];
for(int i=l;i>=1;--i)
id[tax[len[i]]--]=i;
for(int i=l;i>=1;--i)
if(fa[id[i]]) rt[fa[id[i]]]=merge(rt[fa[id[i]]],rt[id[i]]);
}
bool GET_ANS(int l,int r,int _n,int x=1,int RT=1,bool fl=0)
{
if(fl) return 1;
int tt=x>_n?0:a[x]-'a';
for(int i=tt;i<26;++i)
if(son[RT][i]&&ask(1,n,rt[son[RT][i]],l+x-1,r))
{
if(i==a[x]-'a')
{
if(GET_ANS(l,r,_n,x+1,son[RT][i],fl)) return b[++__L]=i+'a',1;
}
else if(GET_ANS(l,r,_n,x+1,son[RT][i],1)) return b[++__L]=i+'a',1;
}
return fl;
}
void Solve(int l,int r,int _n)
{
__L=Fl=0;
if(GET_ANS(l,r,_n))
{
for(int i=__L;i>=1;--i)
printf("%c",b[i]);
printf("\n");
}
else printf("-1\n");
}
}_S;
int main()
{
scanf("%s%d",a+1,&Q),n=strlen(a+1);
for(int i=1;i<=n;++i)
_S.ins(a[i]-'a',i);
_S.Init();
for(int i=1,l,r,_n;i<=Q;++i)
scanf("%d%d%s",&l,&r,a+1),_n=strlen(a+1),_S.Solve(l,r,_n);
return 0;
}
