SRM607 Div2 Medium "PalindromicSubstringsDiv2"

問題

TopCoder Statistics - Problem Statement

訳

マルコは回文というものがあることを知った。回文とは左から読んでも右から読んでも同じになるものである。例えば、"radar"や"racecar"は回文である。

マルコは回文となっている文字列がとても好きであり、特に回文となる部分文字列がたくさん含まれているものが好きである。例えば、彼は"aaa"という文字列がとても好きである。なぜならそれは、"a"という回文が3つ、"aa"という回文が2つ、"aaa"という回文が1つの、6つの回文となる部分文字列が含まれているからだ。

マルコは、全て小文字のSという文字列について考えている。String[] S1, S2が与えられるので、まず下記のようにしてSを得てほしい。

S1の全ての文字列を順番に結合してAという文字列を得る。
S2の全ての文字列を順番に結合してBという文字列を得る。
最後にAとBを結合してSを得る

Sに回文となる部分文字列が何個含まれているかを返せ。

制約

1 <= Sの文字列長 <= 2500

考えたこと

Sの文字列長をNとする。

S[s]からS[t]は回文かどうか確かめてく。が、愚直にやると、回文か確かめるのにNかかり、O(N^3)でぷぎゃーするのでDPする。

dp[s][t] := sからtまでの部分文字列は回文か？

dp[s][t] = (S[s] == S[t] && dp[s+1][t-1])

ソースコード

bool memo[5050][5050];

class PalindromicSubstringsDiv2 {

    public:

    int count(vector <string> S1, vector <string> S2) {
        // Sを作る
        string S = "";
        for (int i = 0; i < S1.size(); i++){
            S += S1[i];
        }
        for (int i = 0; i < S2.size(); i++){
            S += S2[i];
        }
        
        // dp初期化
        int N = S.size();
        int res = 0;
        memset(memo, false, sizeof(memo));
        
        // dp更新（短い部分文字列からやっていく）
        for (int len = 1; len <= N; len++){
            for (int s = 0; s + len - 1 < N; s++){
                int t = s + len - 1;
                // １文字の部分文字列であれば回文
                if (s == t){
                    res++;
                    memo[s][t] = true;
                    continue;
                }

                // S[s]とS[t]が違えば回文作れない
                if (S[s] != S[t]) continue;

                // ２文字の部分文字列であれば回文
                if (s + 1 == t){
                    res++;
                    memo[s][t] = true;
                    continue;
                }

                // memo[s+1][t-1]が回文であれば回文
                if (memo[s + 1][t - 1]){
                    res++;
                    memo[s][t] = true;
                }
            }
        }

        return res;
    }
};