SRM 607 Div1 Easy PalindromicSubstringsDiv1

問題

文字列がいくつか与えられる。これらをすべて連結してできた文字列のうち、'?'をランダムに置き換える。その文字列の部分文字列のうち回文の個数の期待値を求めよ。

文字列長 <= 5000

やりかた

文字を一つ選び、それを中心に文字列を左右に広げていき、それが回文になる時の確率を足していく。あとはこの選ぶ文字をすべての文字にたいして行ったものの和を取る。
確率の求め方はある部分文字列中に、回文中心から同距離にある?ペアの個数がopt個あり、文字列中の?の個数がnum個あるときになる。

部分文字列が偶数の時と奇数の時を考慮する必要があるので、すべての文字と文字の間に適当な文字を入れて、この2種類を一括して扱えるようにする。

以下ソース。

char s[10000];

using namespace std;
class PalindromicSubstringsDiv1 {
public:
  double expectedPalindromes(vector <string> S1, vector <string> S2){
    string t = accumulate(ALL(S1), string("")) + accumulate(ALL(S2), string(""));
    int L = t.length();
    double ans = 0.0;
    for(int i = 0; i < L; i++) 
      s[2 * i] = t[i], s[2 * i + 1] = '-';
    
    L *= 2;
    vector<double> p26(10000, 0);
    p26[0] = 1; for(int i = 1; i < 10000; i++) p26[i] = p26[i - 1] / 26.0;
    for(int i = 0; i < L; i++){
      int k = i % 2;
      int opt = 0, num = 0;
      while(i - k >= 0 && i + k < L){
        //回文でなくなったらそれ以上見ない
	if(isalpha(s[i - k]) && isalpha(s[i + k]) && s[i - k] != s[i + k]) break;
	if(s[i - k] == '?' && s[i + k] == '?') opt++;
	if(s[i - k] == '?' || s[i + k] == '?'){
	  if(k == 0) num++;
	  else num += (s[i - k] == '?') + (s[i + k] == '?');
	}
	ans += p26[num - opt];
	k += 2;
      }
    }
    return ans;
  }
};