*[topcoder]PalindromicSubstringsDiv2

http://community.topcoder.com/stat?c=problem_statement&pm=12967

计算一个字符串里Palindrome的数量。我的DP方法需要n^2的空间。

#include <vector>
#include <string>
using namespace std;class PalindromicSubstringsDiv2 {
public:
int count(vector <string> S1, vector <string> S2) {
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 ret = 0;
vector<vector<bool>> dp;
int N = s.size();
dp.resize(N);
for (int i = 0; i < N; i++) {
dp[i].resize(N + 1);
}
for (int len = 1; len <= N; len++) {
for (int i = 0; i + len <= N; i++) { // start pos
if (len == 1) {
dp[i][len] = true;
} else if (len == 2){
dp[i][len] = (s[i] == s[i + len - 1]);
} else {
dp[i][len] = dp[i + 1][len - 2] && (s[i] == s[i + len - 1]);
}
ret += (dp[i][len] ? 1 : 0);
}
}
return ret;
}
};

如果从中间开始往两边扩，就不需要额外空间了~

#include <vector>
#include <string>
using namespace std;class PalindromicSubstringsDiv2 {
public:
int count(vector <string> S1, vector <string> S2) {
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 count = 0;
int N = s.size();
for (int m = 0; m < N; m++) {
for (int even = 0; even < 2; even++) {
int i, j = 0;
if (even == 0) {
i = j = m;
} else {
i = m;
j = m + 1;
}
for (; i >= 0 && j < N; i--,j++) {
if (s[i] == s[j])
count++;
else
break;
}
}
}
return count;
}
};