双回文串(889499) 题解

做法1：
枚举每一种可能的分割方案，得到前面和后面两个子串，判断这两个子串是不是都是回文串

bool isOk(string S) {
    for (int i = 0; i < S.size(); i++) {
        if (S[i] != S[S.size() - 1 - i]) {
            return false;
        }
    }
    return true;
}

int CountDoublePalindromeString(string S) {
    int n = S.size();
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans += (isOk(S.substr(0, i)) && isOk(S.substr(i)));
    }
    return ans;
}

做法2：
在做法1的基础上可以加一点小优化，不用把子串生成出来，只需要原串上判断某一段下标构成的子串是否是回文串即可。

int CountDoublePalindromeString(string S) {
    int n = S.size();
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        bool ok = true;
        for (int j = 0; j < i; j++) {
            ok &= (S[j] == S[i - 1 - j]);
        }
        for (int j = i; j < n; j++) {
            ok &= (S[j] == S[i + n - 1 - j]);
        }
        ans += ok;
    }
    return ans;
}