SP7258 SUBLEX （后缀自动机）

SUBLEX - Lexicographical Substring Search - 洛谷

给定一个字符串，求本质不同排名第k小的子串

输入格式：

第一行给定主串(len<=90000)

第二行给定询问个数T<=500

随后给出T行T个询问，每次询问排名第k小的串，范围在int内

输出格式：

对于每一个询问，输出T行，每行为排名第k小的串

后缀自动机比较板的一道题，问字串第k小，我们用自动机本身的a-z字典序挨个判断，如果在里面就进去再判断。预处理没见过，我太菜了

void tops(){
	for(int i=1;i<=cnt;i++) a[tre[i].len]++;
	for(int i=1;i<=cnt;i++) a[i]+=a[i-1];
	for(int i=1;i<=cnt;i++) id[a[tre[i].len]--]=i;
	for(int i=cnt;i>=1;i--){
		sz[id[i]]=1;
		for(int j=0;j<26;j++){
			int v=tre[id[i]].ch[j];
			if(!v)continue;
			sz[id[i]]+=sz[v];
		}
	}
}

然后就是说过的第k小：

void query(int k){
   	int x=1;
   	while (k){
   		for (int i=0;i<26;i++){
   			if (tre[x].ch[i]){
   				if (sz[tre[x].ch[i]]>=k){
   					putchar('a'+i);
   					x=tre[x].ch[i];
   					k--;break;
   				}else k-=sz[tre[x].ch[i]];
   			}
   		}
   	}
   	puts("");
}

感觉还是比较好理解的。

#include
using namespace std;
#define int long long
#define ll long long
#define db(x) cerr<<(#x)<<" "<<(x)<<" "<=1;i--){
		sz[id[i]]=1;
		for(int j=0;j<26;j++){
			int v=tre[id[i]].ch[j];
			if(!v)continue;
			sz[id[i]]+=sz[v];
		}
	}
}
void query(int k){
   	int x=1;
   	while (k){
   		for (int i=0;i<26;i++){
   			if (tre[x].ch[i]){
   				if (sz[tre[x].ch[i]]>=k){
   					putchar('a'+i);
   					x=tre[x].ch[i];
   					k--;break;
   				}else k-=sz[tre[x].ch[i]];
   			}
   		}
   	}
   	puts("");
}
string s;
signed main(){
	cin>>s;
	for(auto c:s) ex_sam(c-'a');
	tops();
	int q;cin>>q;
	while(q--){
		int k;cin>>k;query(k);
	}
}