题意：
给一个串S， 多次询问k和m，求S的所有长度为k的不同子串中，字典序为排第m的串的最早出现位置
简化问题：
如果没有长度k的限制，并且没有不同子串的限制要怎么做。要字典序第m大，容易想到用后缀数组，因为它就是将n个后缀按字典序排好的，设f(i) = 排名<=i的所有后缀的所有前缀的个数和，假设答案的串是排名i的后缀的前缀，那么有f(i) >= m 且 f(i-1) < m，则满足二分性，可以二分后缀排名解决。
扩展：
有不同子串的限制，则类似求一个串有多少不同子串那样，对于每个排名为i的后缀的所有前缀，去掉height(i)个前缀即可，同样可以二分。
此时有一个问题，相同的串如何求出最早出现位置？假设找到的答案长度为len，排名为i，如果这个串多次出现，那么只能在排名i...j中连续地出现，其中i<=j且对于所有k属于(i, j]，height[k] >= len，那么最早出现位置就是min(sa[k])，k属于[i, j]，如何得到对应区间[i, j]？二分j，用rmq取区间最小的height判断即可。
回到本题：
有了长度k的限制后，对于每个排名为i的后缀，它的长度必须大于等于k，则n - sa(i) >= k，由子问题知道，如果后缀i可以提供一个不同子串，必须满足height(i) < k。
那么，问题转化为，对于所有的排名i，在满足n - sa(i) >= k 且 height(i) < k 的i中找到一个第m大的i。
有两个限制，容易想到排序，我们按询问k排序，同时对于所有后缀，按height值排序，则可去掉一个条件限制，接下来，我们需要一个数据结构，可以查询第m大的i，且数据可以是动态插入和删除的。
考虑在线段树上二分，线段树叶子节点维护下标i（即排名i)，值为0或1，非叶子节点维护区间和，要找到第m大的i，则从根结点开始跑，设左区间和为sum(l)，则当sum(l) <= k时，答案在左区间里，否则，在右区间里找到第m - sum(l)的数，递归下去即可。另外，对于已经插入到线段树的排名i, 用优先队列维护sa(i), 不满足n - sa(i) >= k时将其删除。
#include<bits/stdc++.h> #define rep(i,e) for(int i=0;i<(e);i++) #define rep1(i,e) for(int i=1;i<=(e);i++) #define repx(i,x,e) for(int i=(x);i<=(e);i++) #define pii pair<int,int> #define X first #define Y second #define PB push_back #define MP make_pair #define mset(var,val) memset(var,val,sizeof(var)) #define scd(a) scanf("%d",&a) #define scdd(a,b) scanf("%d%d",&a,&b) #define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c) #define IOS ios::sync_with_stdio(false);cin.tie(0) using namespace std; typedef long long ll; template <class T> void test(T a){cout<<a<<endl;} template <class T,class T2> void test(T a,T2 b){cout<<a<<" "<<b<<endl;} template <class T,class T2,class T3> void test(T a,T2 b,T3 c){cout<<a<<" "<<b<<" "<<c<<endl;} const int N = 2e6+10; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9+7; struct Node{ int lc,rc; int val; void init(){ lc=rc=val=0; } }tree[N]; int tot; void init(){ tot=1; tree[0].init(); } int update(int i, int l,int r,int pos){ //原本想用区间第k大解决，发现做不了... //所以这个线段树是可持续化的写法（其实只是懒得改） int rt = tot++; tree[rt].init(); tree[rt].val = 1; if(l==r){ return rt; } int mid = l+r>>1; if(pos<=mid){ tree[rt].rc = tree[i].rc; tree[rt].lc = update(tree[i].lc, l,mid,pos); }else { tree[rt].lc = tree[i].lc; tree[rt].rc = update(tree[i].rc, mid+1,r,pos); } tree[rt].val = tree[tree[rt].lc].val + tree[tree[rt].rc].val; return rt; } void del(int i,int l,int r,int pos){ tree[i].val = 0; if(l==r){ return; } int mid = l+r>>1; if(pos<=mid) del(tree[i].lc, l,mid,pos); else del(tree[i].rc,mid+1,r,pos); tree[i].val = tree[tree[i].lc].val + tree[tree[i].rc].val; } int n; int query(int i,int l,int r, int k){ if(tree[i].val < k) return -1; if(l==r) return l; int mid = l+r>>1; int lc = tree[i].lc; if(tree[lc].val >= k){ return query(lc, l,mid,k); }else return query(tree[i].rc, mid+1, r, k-tree[lc].val); } int rnk[N],sa[N], height[N], tmp[N], cnt[N];char s[N]; void suf(int n,int m){ int i,j,k; n++; for(i=0;i<n*2+5;i++)rnk[i]=sa[i]=height[i]=tmp[i]=0; for(i=0;i<m;i++)cnt[i]=0; for(i=0;i<n;i++)cnt[rnk[i]=s[i]]++; for(i=1;i<m;i++)cnt[i]+=cnt[i-1]; for(i=0;i<n;i++)sa[--cnt[rnk[i]]] = i; for(int k = 1;k<=n;k<<=1){ for(i=0;i<n;i++){ int j = sa[i]-k; if(j<0) j+=n; tmp[cnt[rnk[j]]++]=j; } sa[tmp[cnt[0]=0]]=j=0; for(i=1;i<n;i++){ if(rnk[tmp[i]]!=rnk[tmp[i-1]] || rnk[tmp[i]+k]!=rnk[tmp[i-1]+k])cnt[++j]=i; sa[tmp[i]] = j; } memcpy(rnk, sa, n*sizeof(int)); memcpy(sa, tmp, n*sizeof(int)); if(j>=n-1) break; } for(j = rnk[height[i=k=0]=0];i<n-1;i++,k++){ while(~k&&s[i]!=s[sa[j-1]+k]) height[j]=k--,j=rnk[sa[j]+1]; } } struct Query{ int len,k,i; bool operator < (const Query &b)const{ return len<b.len; } }p[N]; pii pos[N]; int ans[N]; int mi[2][N][20]; void rmqinit(){ rep1(i,n){ mi[0][i][0] = height[i]; mi[1][i][0] = sa[i]; } rep(d,2) for(int k = 1;(1<<k)<=n;k++){ for(int i = 1;i+(1<<k)-1<=n;i++){ mi[d][i][k] = min(mi[d][i][k-1], mi[d][i+(1<<k-1)][k-1]); } } } int rmqquery(int l,int r,int d){ int k = log2(r-l+1); return min(mi[d][l][k], mi[d][r-(1<<k)+1][k]); } int rmqquery(int x, int len){ int A = x+1, B = n; int r=x; while(A<=B){ int mid = A+B>>1; if(rmqquery(x+1,mid,0) >= len){ r = mid; A = mid+1; }else B = mid-1; } int l = x; return rmqquery(l,r,1); } void work(){ init(); scanf("%s",s); n = strlen(s); suf(n,128); int q;scd(q); rep(i,q){ int len,k;scdd(len,k); p[i].i = i; p[i].len = len; p[i].k = k; } sort(p,p+q); rep1(i,n){ pos[i] = MP(height[i], i); } sort(pos+1,pos+1+n); int idx = 1; int rt = 0; rmqinit(); priority_queue<int> que; for(int i = 0;i<q;){ int len = p[i].len; while(idx<=n && pos[idx].X < len){ int r = pos[idx].Y; rt = update(rt, 0,n,r); que.push(sa[r]); idx++; } while(!que.empty() && n - que.top() < len){ int top = que.top();que.pop(); del(rt, 0, n, rnk[top]); } while(i<q && p[i].len == len){ int r = query(rt, 0,n,p[i].k); if(r==-1) ans[p[i].i] = -1; else { ans[p[i].i] = rmqquery(r, len); } i++; } } rep(i,q){ if(ans[i]==-1){ puts("Not found"); }else printf("%d ", ans[i]); } } int main() { #ifdef local freopen("in.txt","r",stdin); #endif // local // IOS; int t;scd(t);while(t--) work(); }
如有写的不好或错误的地方，还请指出。如果哪里解释不清楚，欢迎交流和讨论