kmjp's blog

競技プログラミング参加記です

AtCoder ARC #050 : D - Suffix Concat

恐らくwriterの想定誤解法を順調に踏み抜いた。
http://arc050.contest.atcoder.jp/tasks/arc050_d

問題

N文字の文字列Sが与えられる。
Sの全suffixをそれぞれ1個ずつ連結してできる文字列が辞書順最小となるには、どの順でsuffixを連結すればよいか答えよ。

解法

Suffixという言葉につられてSuffix ArrayのRank順でソートしたりすると失敗する。

「文字列群を連結して辞書順最小にする」という場合、その並べ方は定番テクがある。
(AtCoderでも出たことがあるが、残念ながら問題を失念)
文字列群をソートする際、2つの文字列x,yの並び順を決めたいとき、x+y<y+xならxが前に来るようにすればよい。


T[i] := Sのi文字目以降からなるSのsuffix(S[i..N])とする。
上記アイデアをこの問題に適用すると、2つのsuffix T[L],T[R]があったとき、T[L]+T[R]とT[R]+T[L]の辞書順前後判定が高速行えれば良い。

同じ文字列を何度も前後判定する際、高速に判定する手法としてローリングハッシュと二分探索を用いた方法がある。
文字列A,Bの前後判定をするとき、それぞれ部分文字列のハッシュ値を高速に計算できるようローリングハッシュを前準備しておく。
hash(A[0..k])==hash(B[0..k])となる最大のkを二分探索で求めれば、A[k+1]とB[k+1]は異なるはずなのでA[k+1]とB[k+1]の比較でA,B全体の前後判定ができる。

このテクを使えば、T[L]+T[R]とT[R]+T[L]に対する高速な前後判定ができる。
この前後判定関数をSTLのsort関数の述語に使い、suffixの先頭位置をソートすればよい。

struct RollingHash {
	static const ll mo0=1000000007,mo1=1000000009;
	static ll mul0,mul1;
	static const ll add0=1000010007, add1=1003333331;
	static vector<ll> pmo[2];
	string s; int l; vector<ll> hash_[2];
	void init(string s) {
		this->s=s; l=s.size(); int i,j;
		hash_[0]=hash_[1]=vector<ll>(1,0);
		if(!mul0) mul0=10009+(((ll)&mul0)>>5)%259,mul1=10007+(((ll)&mul1)>>5)%257;
		if(pmo[0].empty()) pmo[0].push_back(1),pmo[1].push_back(1);
		FOR(i,l) hash_[0].push_back((hash_[0].back()*mul0+add0+s[i])%mo0);
		FOR(i,l) hash_[1].push_back((hash_[1].back()*mul1+add1+s[i])%mo1);
	}
	pair<ll,ll> hash(int l,int r) { // s[l..r]
		if(l>r) return make_pair(0,0);
		while(pmo[0].size()<r+2)
			pmo[0].push_back(pmo[0].back()*mul0%mo0), pmo[1].push_back(pmo[1].back()*mul1%mo1);
		return make_pair((hash_[0][r+1]+(mo0-hash_[0][l]*pmo[0][r+1-l]%mo0))%mo0,
			             (hash_[1][r+1]+(mo1-hash_[1][l]*pmo[1][r+1-l]%mo1))%mo1);
	}
	pair<ll,ll> hash(string s) { init(s); return hash(0,s.size()-1); }
	static pair<ll,ll> concat(pair<ll,ll> L,pair<ll,ll> R,int RL) { // hash(L+R) RL=len-of-R
		while(pmo[0].size()<RL+2) pmo[0].push_back(pmo[0].back()*mul0%mo0), pmo[1].push_back(pmo[1].back()*mul1%mo1);
		return make_pair((R.first + L.first*pmo[0][RL])%mo0,(R.second + L.second*pmo[1][RL])%mo1);
	}
};
vector<ll> RollingHash::pmo[2]; ll RollingHash::mul0,RollingHash::mul1;

int N;
string S;
int ran[101010];
RollingHash rh;

pair<ll,ll> getrh(int f,int s,int ts) {
	
	if(N-f>=ts) {
		return rh.hash(f,f+ts-1);
	}
	else {
		return rh.concat(rh.hash(f,N-1),rh.hash(s,s+ts-(N-f)-1),ts-(N-f));
	}
}

int comp(int l,int r) {
	
	int len=(N-l)+(N-r);
	int same=0;
	for(int i=20;i>=0;i--) if(same+(1<<i)<=len) {
		int ts=same+(1<<i);
		if(getrh(l,r,ts)==getrh(r,l,ts)) same=ts;
	}
	if(same==len) return 0;
	char c1,c2;
	if(l+same<N) c1=S[l+same];
	else c1=S[r+(same-(N-l))];
	
	if(r+same<N) c2=S[r+same];
	else c2=S[l+(same-(N-r))];
	return c1<c2;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	rh.init(S);
	vector<int> V;
	FOR(i,N) V.push_back(i);
	sort(ALL(V),comp);
	FOR(i,N) _P("%d\n",V[i]+1);
	
}

まとめ

本番T[L]+T[R]とT[R]+T[L]の大小比較が必要なことはわかりつつも、SAで行けるんではと安易に突っ込んで失敗した。
反例を作るのが難しそうで、手元で検証しなかったんだよね…。

まぁDを本番に解けたの久々だし良かったかな。