【SPOJ7258】Lexicographical Substring Search

  对每个状态，预处理出从当前点出发的路径数（也就是不同的子串数），然后直接找第k小字符串就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=90010;

struct SAM
{
	struct State
	{
		int next[26];
		int link;
		int len;
		int sum;
	}st[maxn<<1];

	int cnt,last,n;
	int ccnt[maxn<<1],T[maxn<<1];

	SAM() {cnt=last=1;}

	void Extend(int c)
	{
		int x=++cnt,p;n++;
		st[x].len=st[last].len+1;
		for (p=last;p && !st[p].next[c];p=st[p].link) st[p].next[c]=x;
		if (!p) st[x].link=1;
		else {
			int q=st[p].next[c];
			if (st[q].len==st[p].len+1) st[x].link=q;
			else {
				int v=++cnt;
				st[v]=st[q];
				st[v].len=st[p].len+1;
				for (;p && st[p].next[c]==q;p=st[p].link) st[p].next[c]=v;
				st[x].link=st[q].link=v;
			}
		}
		last=x;
	}

	void PreProcess()
	{
		for (int i=1;i<=cnt;i++) ccnt[st[i].len]++;
		for (int i=1;i<=n;i++) ccnt[i]+=ccnt[i-1];
		for (int i=1;i<=cnt;i++) T[ccnt[st[i].len]--]=i;
		for (int i=cnt;i;i--)
		{
			int x=T[i];
			st[x].sum=1;
			for (int j=0;j<26;j++) st[x].sum+=st[st[x].next[j]].sum;
		}
	}

	void PrintKth(int kth)
	{
		int x=1;
		while (kth)
		{
			for (int i=0;i<26;i++)
				if (kth>st[st[x].next[i]].sum) kth-=st[st[x].next[i]].sum;
				else {
					x=st[x].next[i];
					putchar(i+'a');
					kth--;
					break;
				}
		}
		putchar('\n');
	}
}M;

char ch[maxn];
int n,q;

int main()
{
	scanf("%s",ch);
	n=strlen(ch);
	for (int i=0;i<n;i++) M.Extend(ch[i]-'a');
	M.PreProcess();
	scanf("%d",&q);
	while (q--)
	{
		int x;
		scanf("%d",&x);
		M.PrintKth(x);
	}
	return 0;
}