BZOJ3998: [TJOI2015]弦论 后缀自动机

题解：

先说明，这份代码很不幸的超（ka）时（chang）了。

借这道题目的机会再重新说明一下后缀自动机&后缀树吧。

发现最近一段时间很是习惯于利用后缀树思考问题了，但事实上大概后缀自动机不仅仅是逆序后缀树而已吧。

考虑后缀树，定义$siz_i$表示节点$i$的子树內存在多少个结束节点（即后缀）。

那么对于每个节点$i$，都实际上对应了$len_i-len_{pa_i}$个字符串，长度是从$len_{pa_i}+1-len_i$连续的。

同时这些字符串都会出现$siz_i$次。

为了得到这条边上的字符串，我们需要找出这个节点子树内的任意一个后缀的位置，并利用$len_i$以及$len_{pa_i}$来得到这个节点的所有串。

考虑一个点的若干条儿子边，边代表的字符串的首字母必定不同，我们用首字母字典序大小来决定遍历顺序的先后。

如果想求第$k$小的串，我们就在后缀树上dfs，最终得到是一条边上的第几个串，然后就可以了。

后缀自动机是逆序后缀树，自动机体现在后缀树上的trans指针，即支持在一个字符串上在开头添加一个字符得到新的节点的指针。

由于是反串的后缀树，那么在开头添加一个字符相当于在原串的末尾添加字符。

从根开始，通过若干trans指针会得到一条路径，对于不同字符串，即使路径的最终节点相同，但是路径本身不同。

换言之，我们可以将子串的询问问题转化为拓扑图的路径统计问题。

上面是随便说的。。。

总之，以后考虑字符串的问题时可以从两种方面来考虑：

（1）树结构的后缀树

（2）拓扑图结构的后缀自动机

两种结构各有其优点，并不能像我之前一样完全否定后者。

代码：

#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
using namespace std;

typedef long long ll;
#define N 500010
int tr[N<<1][26],len[N<<1],pa[N<<1],cnt,root,last,siz[N<<1];
ll f[N<<1],g[N<<1];
vector<int>v[N<<1];

inline int newnode(int _len){
	len[++cnt]=_len;
	return cnt;
}

char s[N];
int in[N<<1];
int q[N<<1],fr,ta;
int temp[N<<1];

char ans[N];
int top;

int main(){
	//clock_t begin=clock();
	//freopen("tt.in","r",stdin);
	//freopen("tt.out","w",stdout);
	int n,i,j;
	scanf("%s",s+1);
	n=strlen(s+1);
	int y,p,q,np,nq;
	root=last=newnode(0);
	for(i=1;i<=n;++i){
		np=newnode(len[last]+1);
		for(y=s[i]-'a',p=last;p&&!tr[p][y];p=pa[p])
			tr[p][y]=np;
		if(!p)
			pa[np]=root;
		else{
			if(len[q=tr[p][y]]==len[p]+1)
				pa[np]=q;
			else{
				nq=newnode(len[p]+1);
				pa[nq]=pa[q];
				pa[q]=pa[np]=nq;
				memcpy(tr[nq],tr[q],sizeof tr[q]);
				for(;p&&tr[p][y]==q;p=pa[p])
					tr[p][y]=nq;
			}
		}
		siz[last=np]=1;
	}
	for(i=2;i<=cnt;++i)
		++in[pa[i]];
	for(i=1;i<=cnt;++i)
		if(!in[i])
			::q[ta++]=i;
	while(fr!=ta){
		i=::q[fr++];
		if(pa[i]){
			siz[pa[i]]+=siz[i];
			if(!--in[pa[i]])
				::q[ta++]=pa[i];
		}
	}
	for(i=1;i<=cnt;++i)
		for(j=0;j<26;++j)
			if(tr[i][j]){
				v[tr[i][j]].push_back(i);
				++in[i];
			}
	for(fr=ta=0,i=1;i<=cnt;++i)
		if(!in[i])
			::q[ta++]=i;
	while(fr!=ta){
		i=::q[fr++];
		if(i!=root){
			++f[i];
			g[i]+=siz[i];
		}
		for(j=0;j<v[i].size();++j){
			f[v[i][j]]+=f[i];
			g[v[i][j]]+=g[i];
			if(!--in[v[i][j]])
				::q[ta++]=v[i][j];
		}
	}
	//cout<<f[root]<<endl;
	//cout<<g[root]<<endl;
	int type,k;
	cin>>type>>k;
	if(type==0){
		for(i=2;i<=cnt;++i)
			temp[i]=1;
	}
	else{
		for(i=2;i<=cnt;++i)
			temp[i]=siz[i];
		for(i=1;i<=cnt;++i)
			f[i]=g[i];
	}
	if(k>f[root])
		puts("-1");
	else{
		p=root;
		while(k>0){
			for(int i=0;i<26;++i){
				if(tr[p][i]){
					if(k>f[tr[p][i]])
						k-=f[tr[p][i]];
					else{
						ans[top++]='a'+i;
						k-=temp[p=tr[p][i]];
						break;
					}
				}
			}
		}
	}
	puts(ans);
	//puts("");
	//printf("%ldms",clock()-begin);
	return 0; 

}