Problem Description
You are given a string S consisting of only lowercase english letters and some queries.
For each query (l,r,k), please output the starting position of the k-th occurence of the substring SlSl+1...Sr in S.
For each query (l,r,k), please output the starting position of the k-th occurence of the substring SlSl+1...Sr in S.
Input
The first line contains an integer T(1≤T≤20), denoting the number of test cases.
The first line of each test case contains two integer N(1≤N≤105),Q(1≤Q≤105), denoting the length of S and the number of queries.
The second line of each test case contains a string S(|S|=N) consisting of only lowercase english letters.
Then Q lines follow, each line contains three integer l,r(1≤l≤r≤N) and k(1≤k≤N), denoting a query.
There are at most 5 testcases which N is greater than 103.
The first line of each test case contains two integer N(1≤N≤105),Q(1≤Q≤105), denoting the length of S and the number of queries.
The second line of each test case contains a string S(|S|=N) consisting of only lowercase english letters.
Then Q lines follow, each line contains three integer l,r(1≤l≤r≤N) and k(1≤k≤N), denoting a query.
There are at most 5 testcases which N is greater than 103.
Output
For each query, output the starting position of the k-th occurence of the given substring.
If such position don't exists, output −1 instead.
If such position don't exists, output −1 instead.
Sample Input
2
12 6
aaabaabaaaab
3 3 4
2 3 2
7 8 3
3 4 2
1 4 2
8 12 1
1 1
a
1 1 1
Sample Output
5
2
-1
6
9
8
1
Source
Recommend
SOLUTION:
算板子吧，很好理解
CODE:
#include<bits/stdc++.h>
using namespace std;
int n,q;
const int N = 3e5+10;
char s[N];
int sa[N],c[N];
int t1[N],t2[N];
int height[N];
int r[N];
int RMQ[N];
int mm[N];
int best[50][N];
int Rank[N];
void da(int m )
{
int i,*x=t1,*y=t2;
for(i = 1; i <= m; i++) c[i] = 0;
for(i = 1; i <= n; i++) c[x[i] = s[i]]++;
for(i = 1; i <= m; i++) c[i] += c[i - 1];
for(i = n; i >= 1; i--) sa[c[x[i]]--] = i;
for(int k = 1; k <= n; k <<= 1)
{
int p = 0;
for(i = n - k + 1; i <= n; i++) y[++p] = i;
for(i = 1; i <= n; i++) if(sa[i] > k) y[++p] = sa[i] - k;
for(i = 1; i <= m; i++) c[i] = 0;
for(i = 1; i <= n; i++) c[x[y[i]]]++;
for(i = 1; i <= m; i++) c[i] += c[i - 1];
for(i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
swap(x, y);
p = 1;
x[sa[1]] = 1;
for(i = 2; i <= n; i++)
x[sa[i]] = (y[sa[i]] == y[sa[i - 1]]
&& y[sa[i] + k] == y[sa[i - 1] + k]) ?
p : ++p;
if(p >= n) break;
m = p;
}
}
void getheight()
{
int i, j, k = 0;
for(i = 1; i <= n; i++) Rank[sa[i]] = i;
for(i = 1; i <= n; i++)
{
if(k) k--;
j=sa[Rank[i] - 1];
while(s[j+k] == s[i+k]) k++;
height[Rank[i]] = k;
}
}
void initrmq(int n)
{
mm[0]=-1;
for(int i=1; i<=n; i++)
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
for(int i=1; i<=n; i++)best[0][i]=i;
for(int i=1; i<=25; i++)
{
for(int j=1; j+(1<<i)-1<=n; j++)
{
int a=best[i-1][j];
int b=best[i-1][j+(1<<(i-1))];
if(RMQ[a]<RMQ[b])best[i][j]=a;
else best[i][j]=b;
}
}
}
int askRMQ(int a,int b)
{
int t;
t=mm[b-a+1];
b-=(1<<t)-1;
a=best[t][a];
b=best[t][b];
return RMQ[a]<RMQ[b]?a:b;
}
int lcp(int a,int b)
{
a=Rank[a],b=Rank[b];
if(a>b)swap(a,b);
return height[askRMQ(a+1,b)];
}
int tr[N*70],tot,root[N];
int ls[N*70],rs[N*70];
void cha(int y,int &x,int l,int r,int p)
{
x=++tot;
tr[x]=tr[y]+1;
ls[x]=ls[y],rs[x]=rs[y];
if(l==r)return ;
int mid=l+r>>1;
if(p<=mid)cha(ls[y],ls[x],l,mid,p);
else cha(rs[y],rs[x],mid+1,r,p);
}
int que(int y,int x,int l,int r,int k)
{
if(l==r)return l;
int mid=l+r>>1;
int sum=tr[ls[x]]-tr[ls[y]];
if(k<=sum)return que(ls[y],ls[x],l,mid,k);
else return que(rs[y],rs[x],mid+1,r,k-sum);
}
void Build()
{
tot=0;
memset(tr,0,sizeof tr);
memset(root,0,sizeof root);
memset(ls,0,sizeof ls);
memset(rs,0,sizeof rs);
for(int i=1; i<=n; i++)
cha(root[i-1],root[i],1,n,sa[i]);
}
signed main()
{
int T;
cin>>T;
#define sc(x) scanf("%d",&(x))
while(T--)
{
sc(n);
sc(q);
memset(s,0,sizeof s);
scanf("%s",s+1);
int len=strlen(s+1);
da(250);
getheight();
memset(RMQ,0,sizeof RMQ);
for(int i=1; i<=n; i++)RMQ[i]=height[i];
initrmq(n);
Build();
while(q--)
{
int l,r,k;
sc(l);sc(r);sc(k);
int len=r-l+1;
int up=-1,down=-1;
int L,R;
R=Rank[l]-1;
L=1;
up=Rank[l];
while(L<=R)
{
int mid=L+R>>1;
if(lcp(sa[mid],sa[Rank[l]])<len)
{
L=mid+1;
}
else
{
R=mid-1;
up=mid;
}
}
L=Rank[l]+1;
R=n;
down=Rank[l];
while(L<=R)
{
int mid=L+R>>1;
if(lcp(sa[mid],sa[Rank[l]])<len)
{
R=mid-1;
}
else
{
L=mid+1;
down=mid;
}
}
int x=root[up-1];
int y=root[down];
if(tr[y]-tr[x]<k || down<up)
{
puts("-1");continue;
}
int ans=que(x,y,1,n,k);
cout<<ans<<endl;
}
}
}