SRM607 div2 med PalindromicSubstringsDiv2

TopCoder Statistics - Match Overview

問題概要

• 文字列Sの中に回文が何個あるか

制約

• |S| ≦ 5000

解説

文字列Aが回文の時Aの両サイドに同じ文字が連結した文字列も回文となる。

同じ文字でない文字が連結したらその時点で回文では無くなる。

回文の中心がsiとなるような回文が何個あるかはO(|S|)で求められる。

よって中心の候補はO(|S|)なので、全体の計算量はO(|S|^2)で間に合う。

回文の長さが奇数の時と偶数の時で調べる必要がある。

コード

class PalindromicSubstringsDiv2 {
public:
  int count(vector <string> S1, vector <string> S2) {
    string s = "";
    FOR(i,0,S1.size()) s += S1[i];
    FOR(i,0,S2.size()) s += S2[i];
    int len = s.length();
    int ret = 0;
    // even
    FOR(i,0,len) {
      int l = i, r = i + 1;
      while(l >= 0 && r < len && s[l] == s[r]) {
        ret++;
        l--;
        r++;
      }
    }
    // odd
    FOR(i,0,len) {
      int l = i, r = i;
      while(l >= 0 && r < len && s[l] == s[r]) {
        ret++;
        l--;
        r++;
      }
    }
    return ret;
  }
};