设字符串长度为n，下标从1开始。后缀数组进行排序后，对每个后缀i，它能贡献的不同的字串就是该后缀从\(ht_i+1\)到结尾\(n-sa_i+1\)的所有前缀,利用差分和前缀和预处理出长度小于等于i的子串贡献出的不同字串\(sum_i\)，对每次查询k，可以二分找到它所在长度\(len_k\)和它在所在的长度组中顺序,即\(k-sum_{len_k-1}\)。
可以用扫描线的思想，以长度\(len\)为时间轴，将所有询问k离线按照所在长度组\(len\)排序。用一个树状数组维护1到n的所有后缀（按字典序排序的后缀，在当前的长度\(len\)产生的贡献,每个后缀产生的贡献在\([ht_i+1,n-sa_i+2)\),可以在遍历到这两个端点上时让对应的位置+1或-1。因为在某一长度下，每个后缀产生的贡献为0或者1,而树状数组维护的是前缀和，对当前长度组的每个查询k，可以在树状数组上二分，找到它所在组中的顺序\(k-sum_{len_k-1}\)的位置，即\([1,n]\)中的第\(k-sum_{len_k-1}\)个1的位置,记为j，那么对应到原串就是\(sa_j,sa_j+len-1\)。但到这还没完，题目要求找到第k大的串出现的最左边的位置，因此我们还要在对后缀数组二分，具体来说，对位置j,先二分找到最长的区间\([L,R]\),使得\(LCP(s[sa_i\dots n],s[sa_j\dots n])\ge len,i\in [L,R]\)，然后在用st表查询出\([L,R]\)的\(sa\)的最小值p,，答案即为p,p+len-1
#include<bits/stdc++.h>
#define x first
#define y second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e6+10,M=22;
int m,n;
char s[N];
int sa[N],rk[N],ht[N],RMQ[M][N],lg[N],MIN[M][N],x[N],y[N],c[N];
ll sum[N];
vector<pii>evt[N];
vector<pii>que[N];
void get_sa(int n,int m=255)//m为字符集大小
{
for (int i = 1; i <= n; i ++ ) c[x[i] = s[i]] ++ ;
for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
for (int i = n; i; i -- ) sa[c[x[i]] -- ] = i;//初始化，所有后缀按第一个字母排序
for (int k = 1; k <= n; k <<= 1)
{
int num = 0;
for (int i = n - k + 1; i <= n; i ++ ) y[ ++ num] = i;
for (int i = 1; i <= n; i ++ )
if (sa[i] > k) y[ ++ num] = sa[i] - k;//按第二关键字排序
for (int i = 1; i <= m; i ++ ) c[i] = 0;
for (int i = 1; i <= n; i ++ ) c[x[i]] ++ ;
for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
for (int i = n; i; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;//按第一关键字排序
swap(x, y);
x[sa[1]] = 1, num = 1;
for (int i = 2; i <= n; i ++ )//将有序的序列离散化
x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
if (num == n) break;//所有后缀顺序各不相同
m = num;
}
}
void get_ht(int n){
for(int i=1;i<=n;i++) rk[sa[i]]=i;
for(int i=1,k=0;i<=n;i++){
if(rk[i]==1) continue;
k=max(k-1,0);
int j=sa[rk[i]-1];
while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k]) ++k;
ht[rk[i]]=k;
}
ht[1]=0;
for(int i=2;i<N;i++) lg[i]=lg[i/2]+1;
for(int i=1;i<=n;i++) RMQ[0][i]=ht[i],MIN[0][i]=sa[i];
for(int i=1;i<M;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
RMQ[i][j]=min(RMQ[i-1][j],RMQ[i-1][j+(1<<i-1)]),
MIN[i][j]=min(MIN[i-1][j],MIN[i-1][j+(1<<i-1)]);
}
int LCP(int L,int R){
L++;int k=lg[R-L+1];
return min(RMQ[k][L],RMQ[k][R-(1<<k)+1]);
}
int Min(int L,int R){
int k=lg[R-L+1];
return min(MIN[k][L],MIN[k][R-(1<<k)+1]);
}
template<typename T>
struct Fenwick{
int n;
vector<T> tr;
Fenwick(int n) : n(n), tr(n + 1, T()){}
int lowbit(int x){
return x & -x;
}
void modify(int x, T c){
for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
T query(int x){
T res = T();
for(int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int find(ll p){ //返回前缀和等于p的最小的数
int pos=0;
if(query(n)<p) return -1;
T t=T();
for(int j=M-1;j>=0;j--){
if(pos+(1<<j)<=n&&t+tr[pos+(1<<j)]<p)
{
pos+=1<<j;
t+=tr[pos];
}
}
return pos+1;
}
};
using BIT = Fenwick<ll>;
void solve(){
cin>>s+1;
n=strlen(s+1);
get_sa(n);
get_ht(n);
int Q;
cin>>Q;
BIT tr(n);
for(int i=1;i<=n;i++){
if(ht[i]<n-sa[i]+1){
sum[ht[i]+1]++,sum[n-sa[i]+2]--;
evt[ht[i]+1].push_back({i,1});
evt[n-sa[i]+2].push_back({i,-1});
}
}
for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
for(int i=1;i<=Q;i++){
ll k;
cin>>k;
int l=0,r=n;
while(l<r){
int mid=l+r+1>>1;
if(sum[mid]<k) l=mid;
else r=mid-1;
}
k-=sum[l];
que[l+1].push_back({k,i});
}
vector<pii>ans(Q+1);
for(int i=1;i<=n;i++){
for(auto [x,y]:evt[i]){
tr.modify(x,y);
}
for(auto [x,id]:que[i]){
int t=tr.find(x);
if(t==-1) ans[id]={-1,-1};
else {
int ql=t,qr=t;
if(t>1&&LCP(t-1,t)>=i){
int l=1,r=t-1;
while(l<r){
int mid=l+r>>1;
if(LCP(mid,t)>=i) r=mid;
else l=mid+1;
}
ql=r;
}
if(t<n&&LCP(t,t+1)>=i){
int l=t+1,r=n;
while(l<r){
int mid=l+r+1>>1;
if(LCP(t,mid)>=i) l=mid;
else r=mid-1;
}
qr=r;
}
int tem=Min(ql,qr);
ans[id]={tem,tem+i-1};
}
}
}
for(int i=1;i<=Q;i++){
if(ans[i].x==0) ans[i]={-1,-1};
cout<<ans[i].x<<" "<<ans[i].y<<"\n";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
while(T--) solve();
return 0;
}