AtCoder ARC #044 : D - suffix array

「N≦10^6？もしかして噂のSA-IS知らないと解けない？」とだいぶ頭を抱えていたが、何とか解けた。
http://arc044.contest.atcoder.jp/tasks/arc044_d

問題

N文字の文字列Sに対するsuffix array A[i]が与えられる。
与えられたsuffix arrayを生成する、アルファベット大文字だけで構成された辞書順最小の文字列を答えよ。

解法

S[i]をSのi文字目以降のsuffixとし、Rank(S[i])をそのsuffixのsuffix arrayにおける順位とする。

A[i]文字目が前(A[i-1]文字目)と同じアルファベットで良いか、次のアルファベットを取らないといけないかを順次処理していく。

A[i-1]文字目とA[i]文字目が同じ文字であるならば、Rank(S[A[i-1]+1]) ＜Rank(S[A[i]+1])であるはずである。
そうでないならば、A[i]文字目はA[i-1]文字目の次のアルファベットでなければならない。

int N;
int A[1010101];
int Rank[1010101];
char R[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i],A[i]--,Rank[A[i]]=i+1;
	Rank[N]=0;
	
	char cur='A';
	int pra=0;
	FOR(i,N) {
		if(pra>Rank[A[i]+1]) cur++;
		pra=Rank[A[i]+1];
		R[A[i]]=cur;
		
		if(cur>'Z') return _P("-1\n");
	}
	
	cout<<R<<endl;
}

まとめ

SA-ISいい加減一度チャレンジするかな…。