TopCoder SRM 597 Div1 Easy LittleElephantAndString

久々のSRM。またEasyを凡ミスで落としてレート落とした…。
今回は久しぶりにDiv1 EasyとDiv2 Mediumが同じ問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12854

問題

同じ長さの文字列A,Bが与えられる。
1ターンごとにAのうち任意の１文字を先頭に移動できるとする。
この時、AをBに出来るか、またできるなら必要ターンを最小化せよ。

解法

まず、AとBを構成する文字をカウントし、各文字の数がAとBでずれていたらAをBに出来ない。

AをBにできるとしてターンを最小化するわけだが、できるだけAの並びを維持してBと一致しない部分だけ先頭に回したい。
よって、Aの部分列のうち出来るだけBの末尾と一致するものを残し、それ以外は先頭に回す。

先頭に回す文字数が必要なターン数。
先頭に回す順番は任意なので、同じ文字を２回先頭に回す必要はなく、Bと一致するような順番で先頭に回していけばよい。

class LittleElephantAndString {
	public:
	int getNumber(string A, string B) {
		int i,x,y,r,aa[26];
		int L=A.size();
		ZERO(aa);
		FOR(i,L) aa[A[i]-'A']++;
		FOR(i,L) aa[B[i]-'A']--;
		FOR(i,26) if(aa[i]) return -1;
		
		y=L-1;
		for(x=L-1;x>=0;x--) if(B[y]==A[x]) y--;
		return y+1;
	}
};

まとめ

なぜ添え字をミスった…。