TopCoder SRM 630 Div2 Hard SuffixArrayDiv2

さっきのSuffixArrayDiv1を解ければ簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=13287

問題

アルファベット小文字で構成される文字列Sが与えられる。
SuffixArrayの定義は、Div1 Medium SuffixArrayDiv1と同じとする。
この時、Sと同じSuffixArrayを構成できるより辞書順で小さな文字列は存在するか答えよ。

解法

先のDiv1 Medium SuffixArrayDiv1の解法は、SuffixArrayから辞書順最小となる文字列の生成アルゴリズムそのままである。
よってSからSuffixArrayを生成し、Div1と同じ手順で(最初の文字が'a'となるようにして)文字列を生成し、Sと一致するか見ればよい。

class SuffixArrayDiv2 {
	public:
	string smallerOne(string s) {
		int N=s.size();
		int i,x,y;
		vector<int> SA;
		FOR(i,N) SA.push_back(i);
		FOR(x,N) FOR(y,N-1) if(s.substr(SA[y])>s.substr(SA[y+1])) swap(SA[y],SA[y+1]);
		
		string S=string(N,127);
		
		S[SA[0]]='a';
		for(i=1;i<N;i++) {
			S[SA[i]]=S[SA[i-1]];
			for(int j=i+1;j<N;j++) S[SA[j]]=S[SA[j-1]]+1;
			int ng=0;
			for(x=0;x<i;x++) for(y=x+1;y<=i;y++) if(S.substr(SA[x])>S.substr(SA[y])) ng=1;
			S[SA[i]]+=ng;
		}
		
		if(S<s) return "Exists";
		return "Does not exist";
	}
}

まとめ

こういうDiv1/Div2の問題の分け方は珍しいね。