Description：

给定一个字符串，多次询问排名第 $k$ 小的串。

$1\le len \le 90000$ $1\le n \le 500$

Solution：

可以发现原串每一个本质不同的子串对应后缀自动机上从根节点到某个状态的一条路径，于是可以把 $SAM$ 的 $DAG$ 拓扑排序递推求出 $siz$ ，即代表了从这个状态后面接上一个字符串可以得到原串的多少子串，对于每个询问，直接在 $SAM$ 的当前节点上选一个字典序最小的 $siz\ge k$ 的节点转移过去即可，注意跳过转移要减掉对应的 $siz$ ，因为跳过了对应的子串，还要在到达每个节点时减一，因为跳过了当前字符串，一直到 $k==0$ 时 $break$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

int n;

#define MAXL 90010

char c[MAXL];

struct node

{

	int tr[26],par,maxl;

}s[MAXL << 1];

int root = 1,last = 1,ptr = 1;

int newnode(int k){++ptr;s[ptr].maxl = k;return ptr;}

void extend(int k)

{

	int p = last;

	int np = newnode(s[p].maxl + 1);

	for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

	if(p == 0)s[np].par = root;

	else

	{

		int q = s[p].tr[k];

		if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

		else

		{

			int nq = newnode(s[p].maxl + 1);

			memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

			s[nq].par = s[q].par;

			s[q].par = s[np].par = nq;

			for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

		}

	}

	last = np;

	return;

}

int ind[MAXL << 1];

int siz[MAXL << 1];

vector<int> g[MAXL << 1];

void dp()

{

	queue<int> q;

	for(int i = 1;i <= ptr;++i)

	{

		siz[i] = 1;

		for(int j = 0;j < 26;++j)

		{

			if(s[i].tr[j] != 0)

			{

				++ind[i];

				g[s[i].tr[j]].push_back(i);

			}

		}

		if(ind[i] == 0)q.push(i);

	}

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(vector<int>::iterator it = g[k].begin();it != g[k].end();++it)

		{

			siz[*it] += siz[k];

			--ind[*it];

			if(ind[*it] == 0)q.push(*it);

		}

	}

	return;

}

void find_kth(int k)

{

	int cur = root;

	while(true)

	{

		if(k == 0)break;

		for(int i = 0;i < 26;++i)

		{

			if(k <= siz[s[cur].tr[i]])

			{

				cur = s[cur].tr[i];

				--k;

				putchar(i + 'a');

				break;

			}

			k -= siz[s[cur].tr[i]];

		}

	}

	puts("");

	return;

}

int main()

{

	scanf("%s",c + 1);

	int l = strlen(c + 1);

	for(int i = 1;i <= l;++i)extend(c[i] - 'a');

	dp();

	scanf("%d",&n);

	int k;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&k);

		find_kth(k);

	}

	return 0;

}