题面描述

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 $S_l{S}_{l+1}...S_r$ in $S$.

输入格式

The first line contains an integer $T(1\le T\le 20)$, denoting the number of test cases. The first line of each test case contains two integer $N(1\le N\le 10^5),Q(1\le Q\le 10^5)$, 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\le l\le r\le N)$ and $k(1\le k\le N)$, denoting a query. There are at most $5$ testcases which $N$ is greater than $10^3$.

输入样例

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

输出样例

5 2 -1 6 9 8 1

题面分析

给一个长度为$n$的串，有$q$次询问，每次给一个三元组$(l,r,k)$求S[l,r]出现第k次的位置。 因为$n$很大，对于某个串出现多次的位置判断等可以用后缀数组处理，如果$S[l,n]$和其他任意一个串$q[x,n]$的LCP$\ge$r-l+1，则在$q$中S[l,r]出现过。 因为$q$是有序的，所以我们需要找到符合题意的$q$的范围。 注意到Rank[i]的后缀与其他后缀的LCP随着排名之差绝对值增大而减小，因此我们考虑二分Rank得到满足条件的$q$的Rank上下界$ansL,ansR$。 于是接下来问题变成了如何第k次的下标，下标位置就是SA数组，考虑根据SA数组建立一颗可持久化线段树，然后每次询问$[ansL,ansR]$内的第k个即可。

AC代码（1400ms）

#include <bits/stdc++.h> using namespace std; const int maxn=3e5; #define ll long long namespace SA { int SA[maxn+10];//所有后缀排序后第i小的后缀的起始位置的下标; int Rank[maxn+10];//Rank[i] 第i个后缀的排名,SA[Rank[i]]=Rank[SA[i]]=i int Height[maxn+10]; //Height[i]=排名为i的后缀与排名为(i-1)的后缀的最长公共前缀 //Height[i]>=Height[i-1]+1 //LCP(i,k)=min(LCP(j,j-1)) (1<i<=j<=k<=n) //不同子串的个数:n(n+1)/2-(Height[2]+Height[3]+...+Height[n]) int tax[maxn+10], tp[maxn+10]; //tax[i] 计数排序辅助数组; //tp[i] rk的辅助数组(计数排序中的第二关键字),与SA意义一样。 int len; int s[maxn+10]; int m;//m当前离散后的排名种类数 void RSort() { //rk第一关键字,tp第二关键字 for(int i=0; i<=m; i++) tax[i]=0; for(int i=1; i<=len; i++) tax[Rank[tp[i]]]++; for(int i=1; i<=m; i++) tax[i]+=tax[i-1]; for(int i=len; i>=1; i--) SA[tax[Rank[tp[i]]]--]=tp[i]; //确保满足第一关键字的同时，再满足第二关键字的要求 }//计数排序,把新的二元组排序 int cmp(int *f, int x, int y, int w) { return f[x]==f[y] && f[x+w]==f[y+w]; } //通过二元组两个下标的比较，确定两个子串是否相同 void GetSA() { for(int i=1; i<=len; i++) { Rank[i]=s[i], tp[i]=i; } m=200; RSort(); for(int w=1, p=1, i; p<len; w+=w, m=p) { //把子串长度翻倍,更新rk //w 当前一个子串的长度; //当前的tp(第二关键字)可直接由上一次的SA的得到 for(p=0, i=len-w+1; i<=len; i++) tp[++p]=i; //长度越界,第二关键字为0 for(i=1; i<=len; i++) if (SA[i]>w) tp[++p]=SA[i]-w; //更新SA值,并用tp暂时存下上一轮的rk(用于cmp比较) RSort(), swap(Rank, tp), Rank[SA[1]]=p=1; //用已经完成的SA来更新与它互逆的rk,并离散rk for(i=2; i<=len; i++) Rank[SA[i]]=cmp(tp, SA[i], SA[i-1], w) ? p : ++p; } //离散：把相等的字符串的rk设为相同。 } void GetHeight() { //LCP int j, k=0; for(int i=1; i<=len; Height[Rank[i++]]=k) for(k=k ? k-1 : k, j=SA[Rank[i]-1]; s[i+k]==s[j+k]; ++k); //这个知道原理后就比较好理解程序 } void PrintSA() { for(int i=1; i<=len; i++) { printf("%d ", SA[i]); } printf("\n"); } void PrintHeight() { for(int i=1; i<=len; i++) { printf("%d ", Height[i]); } printf("\n"); } void PrintRank() { for(int i=1; i<=len; i++) { printf("%d ", Rank[i]); } printf("\n"); } } namespace ST { const int logn=30; int f[maxn+10][logn], Log[maxn+10]; void init_log() { Log[0]=-1; Log[1]=0; Log[2]=1; for(int i=3; i<maxn; i++) { Log[i]=Log[i/2]+1; } } void build(int n, int *a) { for(int i=1; i<=n; i++) { f[i][0]=a[i]; } init_log(); for(int j=1; j<=logn; j++) { for(int i=1; i+(1<<j)-1<=n; i++) { f[i][j]=min(f[i][j-1], f[i+(1<<(j-1))][j-1]); } } } int query(int l, int r) { if (l==r) return SA::len-SA::SA[l]; if (l>r) swap(l, r); l++;//这里+1是因为LCP定义!!! int s=Log[r-l+1]; return min(f[l][s], f[r-(1<<s)+1][s]); } } namespace President_Tree { int cnt=0; //cnt:总节点个数 const int Mul=40; int T[maxn+10]; //T:前缀和,T[i]就是1~i中第i颗的根节点 int sum[maxn*Mul+10], L[maxn*Mul+10], R[maxn*Mul+10]; //sum:统计sum[i]对应区间中值域[l',r']个数 //L,R:L[i]指权值线段树中编号为i的左右孩子编号 inline int President_Tree_init() { cnt=0; memset(L, 0, sizeof(L)); memset(R, 0, sizeof(R)); memset(sum, 0, sizeof(sum)); memset(T, 0, sizeof(T)); } inline int build(int l, int r)//和线段树类似 { int rt=++cnt; sum[rt]=0; if (l<r)//这里不执行的时候就是叶子节点 { int mid=(l+r)>>1; L[rt]=build(l, mid); R[rt]=build(mid+1, r); } return rt; } inline int update(int pre, int l, int r, int x) { int rt=++cnt;//开辟新节点 L[rt]=L[pre]; R[rt]=R[pre];// sum[rt]=sum[pre]+1;//更新个数 if (l<r) { int mid=(l+r)>>1; if (x<=mid) L[rt]=update(L[pre], l, mid, x); else R[rt]=update(R[pre], mid+1, r, x); //不断二分开辟新节点，直到对应的点被建立 } return rt;//返回的是上一个被建立的点 } inline int query(int u, int v, int l, int r, int k) //第k大的数,当前左右儿子节点、当前区间、第k大 { if (l>=r) return l; int x=sum[L[v]]-sum[L[u]];//处理左边区间数字个数 int mid=(l+r)>>1; if (x>=k)//左边的区间个数是否到了k return query(L[u], L[v], l, mid, k); return query(R[u], R[v], mid+1, r, k-x); } } char a[maxn+10]; int b[maxn+10]; void solve() { int t; scanf("%d", &t); while(t--) { int len, q; scanf("%d%d", &len, &q); scanf("%s", a+1); for(int i=1; i<=len; i++) { SA::s[i]=a[i]-'a'+1; } SA::len=len; SA::s[len+1]=0; SA::GetSA(); SA::GetHeight(); ST::build(len, SA::Height); for(int i=1; i<=SA::len; i++) { b[i]=SA::SA[i]; } sort(b+1, b+SA::len+1); int cntb=unique(b+1, b+SA::len+1)-(b+1); President_Tree::T[0]=President_Tree::build(1, cntb); for(int i=1; i<=SA::len; i++) { int index=lower_bound(b+1, b+SA::len+1, SA::SA[i])-b; President_Tree::T[i]=President_Tree::update(President_Tree::T[i-1], 1, cntb, index); } while(q--) { int l, r, k; scanf("%d%d%d", &l, &r, &k); int L=1, R=SA::Rank[l]-1; int ansL=SA::Rank[l], ansR=SA::Rank[l]; while(L<=R) { // printf("L=%d R=%d\n", L, R); int mid=(L+R)>>1; if (ST::query(mid, SA::Rank[l])>=r-l+1) { ansL=mid; R=mid-1; } else { L=mid+1; } } L=SA::Rank[l]+1, R=len; while(L<=R) { // printf("L=%d R=%d\n", L, R); int mid=(L+R)>>1; if (ST::query(SA::Rank[l], mid)>=r-l+1) { ansR=mid; L=mid+1; } else { R=mid-1; } } // printf("ansL=%d ansR=%d\n", ansL, ansR); if (ansR-ansL+1<k) { printf("-1\n"); continue; } printf("%d\n", President_Tree::query(President_Tree::T[ansL-1], President_Tree::T[R], 1, cntb, k)); } } } int main() { // ios_base::sync_with_stdio(false); // cin.tie(0); // cout.tie(0); #ifdef ACM_LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); long long test_index_for_debug=1; char acm_local_for_debug; while(cin>>acm_local_for_debug) { cin.putback(acm_local_for_debug); if (test_index_for_debug>100) { throw runtime_error("Check the stdin!!!"); } auto start_clock_for_debug=clock(); solve(); auto end_clock_for_debug=clock(); cout<<"\nTest "<<test_index_for_debug<<" successful"<<endl; cerr<<"Test "<<test_index_for_debug++<<" Run Time: " <<double(end_clock_for_debug-start_clock_for_debug)/CLOCKS_PER_SEC<<"s"<<endl; cout<<"--------------------------------------------------"<<endl; } #else solve(); #endif return 0; }

后记

综合性很强的题，特此记录。 DrGilbert 2020.10.22