TopCoder SRM 607, Division 2, Level 2 : PalindromicSubstringsDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12967&rd=15840

問題概要

　英小文字からなり、長さが 5,000 以下であるような文字列 S が与えられる。S の部分文字列であって、回文となっているものの個数を求めよ。
　

解法

　文字列の長さを L と表記します。
　S の部分文字列を全て取り出して回文かどうかをチェックすると となって間に合いません。より効率のよい方法を考える必要があります。
　ある文字列が回文であるとき、その両端（先頭文字及び末尾文字）を消去した文字列もまた回文となっています。逆に言えば、回文の先頭と末尾に同じ文字を付け足した文字列も回文となります。問題の方で考えると、ある部分文字列が回文であるとき、その両側の文字が等しければそれらを付け足すことでもう一つ回文を作ることができて。両側の文字が等しくないとき、それ以降どうやっても回文となることはありません。
　初期状態（部分文字列の位置）が異なれば異なる部分文字列（共通部分の無い部分文字列の集合）が得られるので、初期状態を全て試して得られる回文の数を足し合わせることで答えが得られます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

class PalindromicSubstringsDiv2
{
public:
	string S;
	int L;

	int count( vector <string> S1, vector <string> S2 )
	{
		{
			S = accumulate( ALL( S1 ), string() ) + accumulate( ALL( S2 ), string() );
			L = S.size();
		}

		int res = 0;
		REP( i, 0, L )
		{
			res += solve( i, i );
			res += solve( i, i + 1 );
		}
		return res;
	}

	int solve( int l, int r )
	{
		int res = 0;
		while ( 0 <= l && r < L )
		{
			if ( S[l] != S[r] )
			{
				return res;
			}
			res++;
			l--, r++;
		}
		return res;
	}
}