TopCoder, SRM 635, Division 2, Level 1 : IdentifyingWood

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13487&rd=16078

問題概要

　二つの文字列 が与えられる。 が を部分列として含むか否か、求めよ。

解法

　 に含まれるある文字にマッチさせられる の文字が複数あるとき、より手前にある文字にマッチさせた方が、後で使える文字が多くなるため有利になります。従って、 の各文字について、 の未使用区間の内最も手前にある同じ文字に対応させることを繰り返すアルゴリズムで最適な戦略をシミュレートできます。このアルゴリズムで、 の全ての文字をマッチさせることができるか否かで、問題の答えを判定できます。
　実装に於いては、 を何文字処理し終わったかを記憶しながら、 を先頭から走査して、走査中、着目している の文字と同じ文字を見つけたら、 に関するインデックスを一つ増やしていくように実装すると楽に書けると思います。

コード

#define FOR( e, c ) for ( auto &e : c )

class IdentifyingWood
{
public:
	string check( string s, string t )
	{
		const int L = t.size();

		int p = 0;
		FOR( c, s )
		{
			p += p < L && t[p] == c;
		}
		return p == L ? "Yep, it's wood." : "Nope.";
	}
};