TopCoder SRM 605, Division 2, Level 1 : AlienAndPassword

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12950&rd=15838

問題概要

　文字列 S が与えられる。S から任意の一文字を削除して得られる相異なる文字列の数を求めよ。

解法

　文字列の長さが 50 以下なので、消すインデックスを全て試すことができます。削除するインデックスを決めたとき、結果の文字列はその位置より手前の部分文字列と後ろの部分文字列を連結したものです。そうしてできた文字列を全て set に入れて size をとることでユニーク要素数を数えることができます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class AlienAndPassword
{
public:
	int getNumber( string S )
	{
		set<string> s;

		REP( i, 0, S.size() )
		{
			s.insert( S.substr( 0, i ) + S.substr( i + 1 ) );
		}
		
		return s.size();
	}
};