AtCoder ABC #138 : E - Strings of Impurity

ABCはそうでもないんだけど、全体的に調子悪め。
https://atcoder.jp/contests/abc138/tasks/abc138_e

問題

文字列S、Tが与えられる。
Sを何度か繰り返した文字列のうち、prefixの部分列としてTを含むようにしたい。
最短で何文字のprefixを取ればよいか。

解法

これは定番問題かな。
Sの部分列として各位置を取ったとき、その次にa～zをそれぞれ取る場合何文字先の文字が最寄であるかを先に前処理として求めておこう。
あとはTの各文字の順で、最寄りの位置に遷移していけばよい。

string S,T;
int nex[201010][26];
int A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	A=S.size();
	B=T.size();
	S=S+S;
	FOR(j,26) nex[2*A][j]=2*A;
	for(i=2*A-1;i>=0;i--) {
		FOR(j,26) nex[i][j]=nex[i+1][j];
		nex[i][S[i]-'a']=i+1;
	}
	
	ll cur=0;
	FORR(c,T) {
		c-='a';
		x=cur%A;
		if(nex[x][c]==2*A) return _P("-1\n");
		cur+=nex[x][c]-x;
	}
	cout<<cur<<endl;
	
}

まとめ

これ旧ABCなら400ptでもいいかとおもうけどね。