TopCoder SRM 604, Division 2, Level 1 : FoxAndWord

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12953&rd=15837

概要

　二つの文字列について、片方を A + B で表したとき、他方が B + A であるようなペアを興味深いペアであるとする。複数の文字列が与えられるので、その文字列集合の中にいくつの興味深いペアがあるか求めよ。

解法

　二つの文字列について、片方の文字列の分割を全て試すことで、そのペアが興味深いペアかどうかを求めることができます。あとは、与えられた文字列集合から二つの組み合わせを全て試して、興味深いペアを数え上げることで解くことができます。

コード

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

class FoxAndWord
{
public:
	int howManyPairs( vector <string> words )
	{
		const int N = words.size();

		int res = 0;
		REP( i, 0, N )
		{
			REP( j, 0, i )
			{
				res += match( words[i], words[j] );
			}
		}
		return res;
	}

	bool match( const string &s1, const string &s2 )
	{
		REP( i, 1, s1.size() )
		{
			const string ss1 = s1.substr( 0, i );
			const string ss2 = s1.substr( i );

			if ( ss2 + ss1 == s2 )
			{
				return true;
			}
		}
		return false;
	}
};