sa_ukuchag.cpp

template<class T>
vector<int>construct_sa(const T &s){
	int n=s.size();
	vector<int>r(n+1),sa(n+1);
	rep(i,n)r[i]=s[i];
	r[n]=-1;
	iota(all(sa),0);
	sort(all(sa),[&](int a,int b){
		return r[a]<r[b];
	});

	vector<int>c(n+1),cnt(n+1);
	vector<int>nsa=sa;
	for(int k=1;k<n;k<<=1){
		for(int i=1;i<=n;i++){
			if(r[sa[i-1]]==r[sa[i]])c[sa[i]]=c[sa[i-1]];
			else c[sa[i]]=i;
		}
		iota(all(cnt),0);
		for(int i=0;i<=n;i++){
			int j=sa[i]-k;
			if(j>=0)nsa[cnt[c[j]]++]=j;
		}
		copy(all(nsa),sa.begin());
		for(int i=1;i<=n;i++){
			r[sa[i]]=r[sa[i-1]];
			if(c[sa[i-1]]!=c[sa[i]]||c[sa[i-1]+k]!=c[sa[i]+k])r[sa[i]]++;
		}
	}
	return sa;
}