题目链接 CF1037H Security
做法：\(\mathbf{SAM}\)，线段树（不用合并）
题意简述给出一个文本串 \(S\) ，有 \(Q\) 次询问，每次询问给出模式串 \(T\) ，问在 \(S\) 串中 \([l,r]\) 区间上是否存在比 \(T\) 的字典序大的子串，如果存在输出其中字典序最小的那个子串，否则输出 \(-1\) 。\(1\le l\le r \le|S|\le10^5,1\le Q,\sum|T|\le 2\times 10^5\) 。
贪心分析首先考虑怎么求最小的比 \(T\) 字典序大的串，不考虑区间限制。设当前 \(T\) 在 \(S\) 上最大匹配长度为 \(len\) 。
\(len = |T|\) ，则在 \(T\) 串后拼上一个字符 \(c\) 肯定比 \(T\) 字典序要大，我们只需在 \(S\) 串中找到一个串为 \(T+c\) ,并使 \(c\) 最小即可。
否则，\(T[1,len]\) 上与 \(S\) 匹配，但是 \(T[1,len+1]\) 不匹配了，我们只需找到一个最小字符 \(c\)，满足 \(c>T[len+1]\) 且 \(T[1,len]+c\) 为 \(S\) 的子串，那么 \(T[1,len]+c\) 就是答案了。如果没找到这样的 \(c\) ,将匹配长度减一，重复进行这个操作。
\(len=0\) 也找不到这样的 \(c\) ,只能输出 \(-1\) 。
可以用反证法证明这种构造方法得到的一定是最小的比 \(T\) 字典序大的串。而要想知道 \(+c\) 后是否是 \(S\) 的子串（即是否存在到 \(c\) 的转移），用 \(\mathbf{SAM}\) 就好啦。
线段树维护二维偏序考虑怎么实现区间限制。我们想知道 \(S[l,r]\) 上是否能匹配子串，自然不能每个区间都建立一个 \(\mathbf{SAM}\)。我们要在原 \(S\) 的 \(\mathbf{SAM}\) 中判断当前匹配到的状态，是否能被 \([l,r]\) 完整包含。一个状态是一些子串的结束位置的集合，如果存在一个结束位置 \(maxPos\) ，满足 \(l \le maxPos-len+1,maxPos\le r\)，（\(len\) 为子串长度），则说明在 \([l,r]\) 区间上有该子串。
观察到如果 \(r\) 固定，使得所有结束位置都小于 \(r\) ，那么我们只需考虑 \(l \le maxPos-len+1\) 部分的限制即可。 \(maxPos\) 越大，\(maxPos-len+1\) 越大，满足单调性，我们只需把一个状态的最大的结束位置找出来作判断即可。这就是经典的二维偏序问题了。我们先将询问按照右端点从小到大排序，将 \(S[1,r]\) 的位置值进线段树，这样找最大结束位置时保证一定是满足 \(maxPos\le r\) 的。
//按照右端点排序，小的在前 sort(ques + 1, ques + 1 + n); for(int i = 1,r = 1;i <= n;i++){ //偏序：让线段树只维护S串中的[1,ques[i].r],这样在check查询时只需判断是否大于左端点ques[i].l即可 for(; r <= ques[i].r; r ++) update(1, 1, dfs_cnt, dfn[id[r]], r); match_t(1, i, 1, ques[i].id); }这里线段树是建立在 \(\mathbf{SAM}\) 的 \(\mathbf{parent}\) 树的 \(\mathbf{dfs}\) 序上的，查询一个状态所有结束位置的最大值 即 查询它的子树上所有状态的结束位置的最大值。把子树转化为一段区间，就可以用线段树友好地进行区间操作了。\(id[i]\) 是一个序列下标到 \(\mathbf{SAM}\) 上状态的映射。然后就是匹配过程了，看完整代码吧~
#include<bits/stdc++.h> using namespace std; #define ls (now<<1) #define rs (now<<1)+1 #define mid (l+r)/2 typedef long long ll; const int N = 1e6+6; const int M = 2e5+6; int n,dfn[N],high[N],dfs_cnt,mx[N << 1],id[N]; int nxt[N][26],link[N],len[N],cnt = 1,las = 1; bool flag[N] = {0}; string ans[M]; char s[N],t[N],*inputT = t; vector<int>a[N]; struct node{ int l,r,id,len; char *t; bool operator<(const node &y )const{return r<y.r;} }ques[N]; void insert(int c,int o){ int cur = ++cnt,p = las; len[cur] = len[las] + 1; las = cur; id[o] = cur; for(; p && !nxt[p][c] ; p = link[p]) nxt[p][c] = cur; if(!p) link[cur] = 1; else{ int q = nxt[p][c]; if(len[q] == len[p] + 1) link[cur] = q; else{ int clone = ++cnt; len[clone] = len[p] + 1; link[clone] = link[q]; link[q] = link[cur] = clone; memcpy(nxt[clone],nxt[q],sizeof(nxt[q])); for(; nxt[p][c] == q;p = link[p]) nxt[p][c] = clone; } } } //求dfs序，now子树范围[dfn[now],high[now]] void dfs(int now){ dfn[now] = ++dfs_cnt; for(auto to:a[now]) dfs(to); high[now] = dfs_cnt; } //普通线段树求区间最大值 void update(int now,int l,int r,int x,int v){ if(l == r) {mx[now] = max(mx[now],v);return;} if(x <= mid) update(ls,l,mid,x,v); else update(rs,mid+1,r,x,v); mx[now] = max(mx[ls],mx[rs]); } int query(int now,int l,int r,int x,int y){ if(x <= l && r <= y) return mx[now]; int an = 0; if(x <= mid) an = query(ls,l,mid,x,y); if(y > mid) an = max(an,query(rs,mid+1,r,x,y)); return an; } //查询在now节点在SAM上的endpos集合中是否存在一点maxPos被[l,r]完整包含 //因为线段树上节点都是小于r的，所以只要满足maxPos-match_len+1 >= l,即说明以maxPos结尾，长度为match_len的串在S串的[l,r]中完整出现 //利用线段树O(lgn)查询now子树上（在dfs序中是一段区间）的S串位置的最大值maxPos bool check(int l,int now,int match_len){ int maxPos = query(1, 1, dfs_cnt, dfn[now], high[now]); if(maxPos - match_len + 1 >= l) return true; else return false; } //now：当前t串已经在SAM匹配的节点，o：查询序号，index:当前要尝试匹配的t串的下标，ans_id离线的答案编号 bool match_t(int now,int o,int index,int ans_id){ //如果已经匹配到t串末尾，尝试在其后放一个字符，如果成功就能与t串拼成一个比t串字典序大的串 if(ques[o].len < index){ for(int i = 0;i < 26;i++) if(nxt[now][i] && check(ques[o].l, nxt[now][i], index)){ flag[ans_id] = 1; //flag标记时候已找到一个比t串字典序大的串 ans[ans_id] += 'a'+ i; return true; } return false; //没拼成 } int c = ques[o].t[index] - 'a'; int next = nxt[now][c]; //如果匹配上了，并且也被[l,r]区间包含了，在后面的匹配中也找到了比t串字典序大的串，这里就拼上与t串匹配的串即可 if(next && check(ques[o].l, next, index) && match_t(next,o,index + 1,ans_id)){ ans[ans_id] += 'a' + c; return true; } //否则，如果能拼上一个比c大的字符，一定也可以得到一个比t串字典序大的串 else{ for(int i = c + 1;i < 26;i++) if(nxt[now][i] && check(ques[o].l, nxt[now][i], index)){ flag[ans_id] = 1; ans[ans_id] += 'a'+ i; return true; } return false; } } int main(){ scanf("%s",s+1); int lens = strlen(s+1); //建SAM for(int i = 1;i <= lens;i++) insert(s[i]-'a',i); //parent树连边，建立dfs序 for(int i = 1;i <= cnt;i++) a[link[i]].push_back(i); dfs(1); scanf("%d",&n); //用inputT指针串联起字符串，防止开多个字符串爆内存 for(int i = 1;i <= n;i++){ scanf("%d %d %s", &ques[i].l, &ques[i].r, inputT + 1); ques[i].t = inputT; ques[i].id = i; ques[i].len = strlen(ques[i].t + 1); inputT += ques[i].len + 1; } //按照右端点排序，小的在前 sort(ques + 1, ques + 1 + n); for(int i = 1,r = 1;i <= n;i++){ //偏序：让线段树只维护S串中的[1,ques[i].r],这样在check查询时只需判断是否大于左端点ques[i].l即可 for(; r <= ques[i].r; r ++) update(1, 1, dfs_cnt, dfn[id[r]], r); match_t(1, i, 1, ques[i].id); } for(int i = 1;i <= n;i++) { if(!flag[i]) printf("-1\n"); else{ //倒序输出字符串 int l = ans[i].size(); for(int j = l - 1;j >= 0;j-- ) printf("%c",ans[i][j]); printf("\n"); } } return 0; }