TopCoder SRM 607 Div1 Easy PalindromicSubstringsDiv1

問題

文字列sの回文度とは、sの空でない連続する部分文字列のうち、回文であるものの個数を言う。
英小文字と'?'からなる文字列sが与えられる。
文字列中の'?'は等確率でa-zに変化する。このとき、sの回文度の期待値を求めよ。

制約条件

sの長さ≦5000

方針

回文を中心から伸ばしていくだけ。
長さが偶数奇数の場合にわけて、中心を全部試せばいい。

?と?、または?と文字が出たら確率は1/26。
違う文字が出たら確率は0になる。

ソースコード

class PalindromicSubstringsDiv1 {
	public:
	double expectedPalindromes(vector <string> S1, vector <string> S2) {
		string s;
		rep(i, S1.size()) s += S1[i];
		rep(i, S2.size()) s += S2[i];
		
		double ans = 0;
		rep(i, s.size()){
			double p = 1;
			//odd
			ans++;
			for(int j = 1; ; j++){
				if(i < j || i + j >= s.size()) break;
				int q = (s[i - j] == '?') + (s[i + j] == '?');
				if(q == 0 && s[i - j] != s[i + j]) break;
				if(q != 0) p /= 26;
				
				ans += p;
			}
			p = 1;
			//even
			for(int j = 0; ; j++){
				if(i < j || i + 1 + j >= s.size()) break;
				int q = (s[i - j] == '?') + (s[i + j + 1] == '?');
				if(q == 0 && s[i - j] != s[i + j + 1]) break;
				if(q != 0) p /= 26;
				
				ans += p;
			}
		}
		return ans;
	}
};