暴力法会超时，dp[i][j] 表示 子串 [i...j] 是否为回文串。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define CHECKTIME() printf(%.2lf , (double)clock() / CLOCKS_PER_SEC) /*************** Program Begin **********************/ bool dp[5000][5001]; class PalindromicSubstringsDiv2 { public: int count(vector S1, vector S2) { memset(dp, 0, sizeof(dp)); int res = 0; string S; for (int i = 0; i < S1.size(); i++) { S += S1[i]; } for (int i = 0; i < S2.size(); i++) { S += S2[i]; } int N = S.size(); for (int i = 0; i < N; i++) { dp[i][i] = true; ++res; } for (int len = 2; len <= N; len++) { for (int i = 0; i <= N - len; i++) { if (S[i] == S[i + len - 1]) { if (len == 2 || dp[i+1][i + len - 2] == true) { dp[i][i+ len - 1] = true; ++res; } } } } return res; } }; /************** Program End ************************/