CF1037H Security

· · 题解

\text{Solution}

首先对于字典序最小，我们可以来个贪心：

假如是 aab ，那么我们先考虑能不能在 [L,R] 内匹配到 aab ，再考虑能否再添上一个最小的字母。假如不行，返回上一步，找一个大于 b 的最小字母，凑出来就字典序最大了。不行的话就再回跳。

总结下：

  1. 假如前面全部一模一样匹配成功，且全部匹配完，只需要看能否添上一个最小的即可。

  2. 看能否当前位匹配一样的。

  3. 能否匹配更大的，直接退出。

注意下，它们是有优先级的。

那么，对于一个字符串，我们怎么考虑它是否在 [L,R] 出现？

考虑当前匹配到 SAM 的 p 节点，然后 SAM 的父亲是儿子的后缀，说明父亲这个状态在儿子中都有出现过，那么我们只需要判断下这个子树里有没有在 [L,R] 之中的即可。

这里我线段树合并不熟，写了个主席树+dfs序。

\text{Code}

#include <bits/stdc++.h>

#define N (int)(3e5+5)

using namespace std;

struct edge {
    int nex,to;
}e[N];

char s[N];
int head[N],cnt,sz[N],val[N],fa[N],len[N],son[26][N],id[N],rk[N],rt[N],id_tot;
int n,m,M,las=1,tot=1;

void add_edge(int x,int y) {
    e[++cnt].nex=head[x]; e[cnt].to=y;
    head[x]=cnt;
}

void ins(int c,int v) {
    int pre=las,x=++tot; las=x; len[x]=len[pre]+1; val[x]=v; 
    for(;pre&&!son[c][pre];pre=fa[pre]) son[c][pre]=x;
    int y=son[c][pre];
    if(!pre) fa[x]=1;
    else if(len[pre]+1==len[y]) fa[x]=y;
    else {
        int p=++tot; len[p]=len[pre]+1;
        fa[p]=fa[y]; fa[x]=fa[y]=p;
        for(int i=0;i<26;i++) son[i][p]=son[i][y];
        for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=p;
    }
    //return x;
}

int dtot=0;
void dfs(int x) {
    id[x]=++dtot; rk[dtot]=x; sz[x]=1;
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        dfs(y); sz[x]+=sz[y];
    }
}

int ls[N*30],rs[N*30],sum[N*30],pos_tot=0;

void update(int &cur,int pre,int l,int r,int x) {
    if(!cur) cur=++pos_tot;
    sum[cur]=sum[pre]+1;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(x<=mid) rs[cur]=rs[pre],update(ls[cur],ls[pre],l,mid,x);
    else ls[cur]=ls[pre],update(rs[cur],rs[pre],mid+1,r,x);
}

int query(int pre,int cur,int l,int r,int x) {
    if(l==r&&l==x) return sum[cur]-sum[pre];
    if(l==r) return 0;
    int mid=(l+r)>>1;
    if(x<=mid) return query(ls[pre],ls[cur],l,mid,x);
    else return sum[ls[cur]]-sum[ls[pre]]+query(rs[pre],rs[cur],mid+1,r,x);
}

char ans[N];
int ans_tot=0;

bool check(int x,int L,int R) {
    int l=id[x],r=id[x]+sz[x]-1;
//  cout<<(char)(x+'a')<<' '<<L<<" "<<R<<" "<<query(rt[l-1],rt[r],1,n,R)-query(rt[l-1],rt[r],1,n,L-1)<<'\n';
    return query(rt[l-1],rt[r],1,M,R)-query(rt[l-1],rt[r],1,M,L-1)>0;
}

bool solve(int p,int x,int l,int r) {   
    if(x==n+1) {    
        for(int i=0;i<26;i++) {
            if(son[i][p]&&check(son[i][p],l,r)) {
                ans_tot=x; ans[ans_tot]=i; return 1;
            }
        }
        return 0;
    }
    bool fl=0;
    if(son[s[x]-'a'][p]) {
        int t=son[s[x]-'a'][p];
        if(check(t,l,r)) fl=solve(t,x+1,l+1,r);
        if(fl) ans[x]=s[x]-'a';
    }       
    if(fl) return 1;                                                                
    for(int i=s[x]-'a'+1;i<26;i++) {
        if(son[i][p]&&check(son[i][p],l,r)) {
            ans_tot=x; ans[x]=i; return 1;
        }
    }
    return 0;
}

int main() {
    scanf("%s%d",s+1,&m); M=n=strlen(s+1);
    for(int i=1;i<=n;i++) ins(s[i]-'a',i);
    for(int i=2;i<=tot;i++) add_edge(fa[i],i);
    dfs(1); //build(1,1,tot);
    for(int i=1;i<=tot;i++) {
        if(val[rk[i]]) update(rt[i],rt[i-1],1,n,val[rk[i]]);
        else rt[i]=rt[i-1];
    }
    for(int i=1;i<=m;i++) {
        int L,R;
        scanf("%d%d%s",&L,&R,s+1); n=strlen(s+1); ans_tot=0;
        if(solve(1,1,L,R)) {
            for(int i=1;i<=ans_tot;i++) printf("%c",ans[i]+'a');
            puts("");
        } else puts("-1");
    }
    return 0;
}