yukicoder : No.1192 半部分列

まだ全部は解いてないけど。
https://yukicoder.me/problems/no/1192

問題

文字列S,Tが与えられる。
Sの部分列のうちTの部分列でないもので、辞書順最小のものを求めよ。

解法

まず前処理として以下を求めておく。iは0-originとする。
f(i,c) := Sのi文字目以降で最初に文字cが登場する場所+1
g(i,c) := Tのi文字目以降で最初に文字cが登場する場所+1
h(i) := Sのi文字目以降をすべて含むようなTの最小のSuffixの開始位置。存在しなければ-1とする。

SがTの部分列である場合、どうやっても条件を満たせない。
そこでh(0)≧0であることは最初に確認しておく。
辞書順最小のものを求めるので、以下の手順で行おう。

初期値として、x=y=0とする。
もし次に解としてSのx文字目以降にある最初のcを取ることを考える。
その場合、次の文字はf(x,c)文字目を拾うことになる。
また、その時そこまでTのy文字目までを解に取り込んでいた場合、T側はg(y,c)文字目を拾う。
この時、Sのf(x,c)文字目以降がTのg(y,c)文字目以降の部分列になっていては困るので、そうでないようにしたい。
これはg(y,c)＞h(f(x,c))をチェックすれば判定できる。

cを小さい順に総当たりし、状態を満たすcを見つけたらその文字を解に取り込み、x := f(x,c)、 y := g(y,c)と状態を更新しよう。

int A,B;
string S,T;

int po[202020];
int nexS[202020][26];
int nexT[202020][26];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	A=S.size();
	B=T.size();
	
	MINUS(po);
	po[A]=B;
	x=A;
	for(i=B-1;i>=0;i--) {
		if(x&&S[x-1]==T[i]) {
			x--;
			po[x]=i;
		}
	}
	
	FOR(i,26) nexS[A][i]=A+1;
	FOR(i,26) nexT[B][i]=nexT[B+1][i]=B+1;
	for(i=A-1;i>=0;i--) {
		FOR(j,26) nexS[i][j]=nexS[i+1][j];
		nexS[i][S[i]-'a']=i+1;
	}
	for(i=B-1;i>=0;i--) {
		FOR(j,26) nexT[i][j]=nexT[i+1][j];
		nexT[i][T[i]-'a']=i+1;
	}
	
	if(po[0]>=0) {
		cout<<-1<<endl;
		return;
	}
	
	string R;
	x=y=0;
	while(x<A) {
		FOR(i,26) {
			int x2=nexS[x][i];
			int y2=nexT[y][i];
			if(x2<=A&&y2>po[x2]) {
				R+='a'+i;
				x=x2;
				y=y2;
				break;
			}
		}
		if(y>=B+1) break;
		if(i==26) break;
	}
	
	if(R.empty()) R="-1";
	cout<<R<<endl;
	
}

まとめ

ありそうで意外になかった問題？