Solution 【后缀自动机|[Codeforces] 1037 H. Security 后缀自动机+主席树】这题思路还是比较简单的。
由于 ∑ ∣ S ∣ \sum|S| ∑∣S∣较小，所以可以枚举答案前多少位是和给出的串是一样的，再枚举下一位填什么，这样问题就转化为快速判断一个区间中某个字符串是否出现过。
把parent树建出来后，就是询问某个点子树中有没有值域在某个范围内的点，可以用主席树解决。
需要注意的是，当询问长度为 l e n len len的串是否在 [ l , r ] [l,r] [l,r]中出现时，询问的是 [ l + l e n ? 1 , r ] [l+len-1,r] [l+len?1,r]的线段树，因为这样才能保证串没有越界。
Code
#include
using namespace std;
#define LL long long
#define pa pair
const int Maxn=100010;
const int inf=2147483647;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
int q,n,ed[Maxn];
char s[Maxn],str[Maxn<<1];
int son[Maxn<<1][26],par[Maxn<<1],mx[Maxn<<1];
int lst=1,tot=1;
void extend(int x)
{
int p=lst,np=++tot;
mx[np]=mx[p]+1;
while(p&&!son[p][x])son[p][x]=np,p=par[p];
if(!p)par[np]=1;
else
{
int q=son[p][x];
if(mx[p]+1==mx[q])par[np]=q;
else
{
int nq=++tot;
mx[nq]=mx[p]+1;
for(int i=0;
i<26;
i++)son[nq][i]=son[q][i];
par[nq]=par[q];
par[q]=par[np]=nq;
while(son[p][x]==q)son[p][x]=nq,p=par[p];
}
}
lst=np;
}
int c[Maxn*60],lc[Maxn*60],rc[Maxn*60],root[Maxn<<1];
int cnt=0;
void insert(int&u,int l,int r,int p)
{
if(!u)u=++cnt;
c[u]++;
if(l==r)return;
int mid=l+r>>1;
if(p<=mid)insert(lc[u],l,mid,p);
else insert(rc[u],mid+1,r,p);
}
void merge(int&u1,int u2)
{
if(!u1){u1=u2;
return;
}
if(!u2)return;
c[u1]+=c[u2];
merge(lc[u1],lc[u2]),merge(rc[u1],rc[u2]);
}
int query(int L,int R,int l,int r,int ql,int qr)
{
if(!R)return 0;
if(ql==l&&qr==r)return c[R]-c[L];
int mid=l+r>>1;
if(qr<=mid)return query(lc[L],lc[R],l,mid,ql,qr);
if(ql>mid)return query(rc[L],rc[R],mid+1,r,ql,qr);
return query(lc[L],lc[R],l,mid,ql,mid)+query(rc[L],rc[R],mid+1,r,mid+1,qr);
}
struct Edge{int y,next;
}e[Maxn<<1];
int last[Maxn<<1],len=0;
void ins(int x,int y)
{
int t=++len;
e[t].y=y;
e[t].next=last[x];
last[x]=t;
}
int in[Maxn<<1],out[Maxn<<1],dfn=0;
void dfs(int x)
{
in[x]=++dfn;
for(int i=last[x];
i;
i=e[i].next)dfs(e[i].y);
out[x]=dfn;
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;
i<=n;
i++)extend(s[i]-'a'),ed[i]=lst;
q=read();
for(int i=2;
i<=tot;
i++)ins(par[i],i);
dfs(1);
root[0]=0;
for(int i=1;
i<=n;
i++)insert(root[i],1,tot,in[ed[i]]),merge(root[i],root[i-1]);
while(q--)
{
int l=read(),r=read();
scanf("%s",str+1);
int m=strlen(str+1);
bool flag1=false,flag2=false;
int x=1,u=-1;
for(int i=1;
i<=m;
i++)
{
int t=str[i]-'a';
bool flag=false;
for(int j=t+1;
j<26;
j++)
if(son[x][j])
{
int o=son[x][j];
if(query(root[l+i-2],root[r],1,tot,in[o],out[o]))
{
flag=true;
break;
}
}
if(flag)u=x;
if(i==r-l+1)break;
int o=son[x][t];
if(!query(root[l+i-2],root[r],1,tot,in[o],out[o]))break;
x=o;
if(i==m)flag2=true;
}
if(flag2)
{
bool flag=false;
for(int j=0;
j<26;
j++)
if(son[x][j])
{
int o=son[x][j];
if(query(root[l+m-1],root[r],1,tot,in[o],out[o]))
{
flag=true;
break;
}
}
if(flag)u=x,flag1=true;
}
if(u==-1)puts("-1");
else
{
x=1;
for(int i=1;
i<=m;
i++)
{
int t=str[i]-'a';
if(u==x)
{
for(int j=t+1;
j<26;
j++)
if(son[x][j])
{
int o=son[x][j];
if(query(root[l+i-2],root[r],1,tot,in[o],out[o]))
{
printf("%c",j+'a');
break;
}
}
break;
}
printf("%c",str[i]);
x=son[x][t];
}
if(flag1)
{
for(int j=0;
j<26;
j++)
if(son[x][j])
{
int o=son[x][j];
if(query(root[l+m-1],root[r],1,tot,in[o],out[o]))
{
printf("%c",j+'a');
break;
}
}
}
puts("");
}
}
}
推荐阅读
- 主席树|HDU4417（主席树）
- 【后缀自动机】 CodeForces 235C Cyclical Quest
- 主席树|191101CSP模拟题解
- 主席树|[LOJ]#2720. 「NOI2018」你的名字 后缀自动机+主席树