题目概述

CF1037H

解题报告

算法不难得出：对于 $x$ 的每个前缀 $x[1,i]$ ，往后添加一个比 $x_{i+1}$ 大的字符 $ch$ ，$i$ 越大 $ch$ 越小得到的答案就越小。

因此只需要考虑 $x[1,i]+ch$ 在 $s[L,R]$ 中是否出现过，对 $s$ 建SAM后求出 $Right$ 集合即可查询。

复杂度 $O(26|x|\log_2|S|)$ 。

示例程序

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=100000,maxl=200000,maxs=maxn<<1,maxt=1e7,maxi=26;

int te,n,m;char s[maxl+5];
struct SAM{
    int pl,ro,son[maxs+5][maxi],MAX[maxs+5],fai[maxs+5],pos[maxs+5];
    int newnode() {pl++;return pl;}
    SAM() {pl=0;ro=newnode();}
    int Extend(int p,int c,int id){
        int np=newnode();MAX[np]=MAX[p]+1;pos[np]=id;
        while (p && !son[p][c]) son[p][c]=np,p=fai[p];
        if (!p) {fai[np]=ro;return np;}
        int q=son[p][c];if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;}
        int nq=newnode();MAX[nq]=MAX[p]+1;
        for (int i=0;i<maxi;i++) son[nq][i]=son[q][i];
        fai[nq]=fai[q];fai[q]=fai[np]=nq;
        while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
        return np;
    }
}SAM;
vector<int> e[maxs+5];
int pl,ro[maxs+5],ls[maxt+5],rs[maxt+5],sum[maxt+5];

int newnode() {pl++;return pl;}
int Insert(int p,int pos,int l=1,int r=n){
    int now=newnode();
    ls[now]=ls[p];rs[now]=rs[p];sum[now]=sum[p]+1;
    if (l==r) return now;
    int mid=l+(r-l>>1);
    pos<=mid?ls[now]=Insert(ls[p],pos,l,mid):rs[now]=Insert(rs[p],pos,mid+1,r);
    return now;
}
int Merge(int x,int y){
    if (!x && !y) return 0;
    int now=newnode();
    if (!x || !y){
        ls[now]=ls[x+y];rs[now]=rs[x+y];sum[now]=sum[x+y];
        return now;
    }
    ls[now]=Merge(ls[x],ls[y]);
    rs[now]=Merge(rs[x],rs[y]);
    sum[now]=sum[ls[now]]+sum[rs[now]];
    return now;
}
void DFS(int x){
    if (SAM.pos[x]) ro[x]=Insert(ro[x],SAM.pos[x]);
    for (auto u:e[x]) DFS(u),ro[x]=Merge(ro[x],ro[u]);
}
int Ask(int p,int L,int R,int l=1,int r=n){
    if (!p) return 0;
    if (L==l && r==R) return sum[p];
    int mid=l+(r-l>>1);
    if (R<=mid) return Ask(ls[p],L,R,l,mid); else if (L>mid) return Ask(rs[p],L,R,mid+1,r);
    else return Ask(ls[p],L,mid,l,mid)+Ask(rs[p],mid+1,R,mid+1,r);
}
int main(){
    scanf("%s",s+1);n=strlen(s+1);
    for (int i=1,p=SAM.ro;i<=n;i++) p=SAM.Extend(p,s[i]-'a',i);
    for (int i=2;i<=SAM.pl;i++) e[SAM.fai[i]].push_back(i);
    DFS(SAM.ro);
    for (scanf("%d",&te);te;te--){
        int L,R;
        scanf("%d%d%s",&L,&R,s+1);
        m=strlen(s+1);
        int len=-1,p=SAM.ro,ch;
        for (int i=1;i<=m;i++){
            for (int j=s[i]-'a'+1;j<maxi;j++)
                if (SAM.son[p][j] && Ask(ro[SAM.son[p][j]],L+i-1,R))
                    {len=i-1;ch=j;break;}
            p=SAM.son[p][s[i]-'a'];
            if (!Ask(ro[p],L+i-1,R)) {p=0;break;}
        }
        if (p){
            for (int j=0;j<maxi;j++)
                if (SAM.son[p][j] && Ask(ro[SAM.son[p][j]],L+m,R))
                    {len=m;ch=j;break;}
        }
        if (len<0) puts("-1"); else {
            for (int i=1;i<=len;i++) putchar(s[i]);
            putchar(ch+'a');puts("");
        }
    }
    return 0;
}