Codeforces 1037H Security

字典序最小又要是子串，显然可以不保留答案中与询问串首次字符不相同的位置之后的所有字符。
即考虑对于询问串的每个前缀，考虑在其后加一个比原字符大的字符，并判断是否为子串。

而要一边跑前缀一边匹配的数据结构只有后缀自动机了（当然可以用别的思路用 SA 做
所以后缀自动机上线段树合并维护一下区间即可。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5;
int n,m,q;
char s[N + 5],t[(N << 1) + 5];
int dir[(N << 1) + 5],ans;
namespace SEG
{
    struct node
    {
        int ls,rs;
    } seg[(N << 7) + 10];
    int tot;
    void insert(int x,int &p,int tl,int tr)
    {
        !p && (p = ++tot);
        if(tl == tr)
            return ;
        int mid = tl + tr >> 1;
        x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
    }
    int merge(int x,int y)
    {
        if(!x || !y)
            return x | y;
        int p = ++tot;
        seg[p].ls = merge(seg[x].ls,seg[y].ls),seg[p].rs = merge(seg[x].rs,seg[y].rs);
        return p;
    }
    int query(int l,int r,int p,int tl,int tr)
    {
        if(!p)
            return 0;
        if(l <= tl && tr <= r)
            return 1;
        int mid = tl + tr >> 1;
        int ret = 0;
        l <= mid && (ret |= query(l,r,seg[p].ls,tl,mid));
        r > mid && (ret |= query(l,r,seg[p].rs,mid + 1,tr));
        return ret;
    }
}
namespace SAM
{
    struct node
    {
        int ch[26];
        int fa,len,rt;
    } sam[(N << 1) + 5];
    int las = 1,tot = 1;
    int c[N + 5],a[(N << 1) + 5];
    inline void insert(int x)
    {
        int cur = las,p = ++tot;
        sam[p].len = sam[cur].len + 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt,sam[nxt].rt = 0;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        SEG::insert(sam[p].len,sam[las = p].rt,1,n);
    }
    inline void build()
    {
        for(register int i = 1;i <= tot;++i)
            ++c[sam[i].len];
        for(register int i = 1;i <= n;++i)
            c[i] += c[i - 1];
        for(register int i = tot;i > 1;--i)
            a[c[sam[i].len]--] = i;
        for(register int i = tot;i > 1;--i)
            sam[sam[a[i]].fa].rt = SEG::merge(sam[sam[a[i]].fa].rt,sam[a[i]].rt);
    }
}
int main()
{
    scanf("%s%d",s + 1,&q),n = strlen(s + 1);
    for(register int i = 1;i <= n;++i)
        SAM::insert(s[i] - 'a');
    SAM::build();
    int l,r;
    for(;q;--q)
    {
        scanf("%d%d%s",&l,&r,t + 1),m = strlen(t + 1),memset(dir + 1,-1,sizeof(int) * (m + 1)),t[m + 1] = 'a' - 1,ans = 0;
        for(register int i = 1,p = 1;i <= m + 1;p = SAM::sam[p].ch[t[i++] - 'a'])
        {
            for(register int j = t[i] - 'a' + 1;j < 26;++j)
                if(SAM::sam[p].ch[j] && SEG::query(l + i - 1,r,SAM::sam[SAM::sam[p].ch[j]].rt,1,n))
                {
                    dir[i] = j;
                    break;
                }
            if(i == m + 1 || !SAM::sam[p].ch[t[i] - 'a'] || !SEG::query(l + i - 1,r,SAM::sam[SAM::sam[p].ch[t[i] - 'a']].rt,1,n))
                break;
        }
        for(register int i = m + 1;i;--i)
            if(~dir[i])
            {
                ans = i;
                break;
            }
        if(ans)
        {
            for(register int i = 1;i < ans;++i)
                putchar(t[i]);
            putchar(dir[ans] + 'a'),puts("");
        }
        else
            puts("-1");
    }
}