Pagini recente » Cod sursa (job #2772218) | Cod sursa (job #380376) | Cod sursa (job #1668842) | Cod sursa (job #2796030) | Cod sursa (job #680521)
Cod sursa(job #680521)
// http://infoarena.ro/problema/pscpld
#include <fstream>
#include <string>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int MAXSIZE = 10000;
int size,answer;
bool best[2*MAXSIZE+1];
string text;
int length(double center);
int subsequences(double center);
string longestPalindromeDP(string s);
int main() {
in >> text;
//out << text;
size = text.length() - 1;
//out << longestPalindromeDP(text);
for(double i=1.0;i<size;i+=0.5)
answer += subsequences(i);
/*for(int i=0;i<=size;i++) {
for(int k=0;k<=size;k++)
out << best[i][k] << " ";
out << "\n";
}*/
out << answer + 2 << "\n";
return (0);
}
int length(double center) {
int left = 0;
int right = 0;
int value = 0;
if((int)center == center) {
left = (int)center - 1;
right = (int)center + 1;
value = 1;
}
else {
left = (int)(center - 0.5);
right = (int)(center + 0.5);
}
do {
if(text[left] == text[right])
value += 2;
else
break;
left--,right++;
} while (0 <= left && right <= size);
return value;
}
int subsequences(double center) {
int left = 0;
int right = 0;
int value = 0;
if((int)center == center) {
left = (int)center - 1;
right = (int)center + 1;
value = 1;
}
else {
left = (int)(center - 0.5);
right = (int)(center + 0.5);
}
do {
if(text[left] == text[right])
value++;
else
break;
left--,right++;
} while (0 <= left && right <= size);
return value;
}
string longestPalindromeDP(string s) {
int n = s.length();
int longestBegin = 0;
int maxLen = 1;
bool table[1000][1000] = {false};
for (int i = 0; i < n; i++) {
table[i][i] = true;
}
for (int i = 0; i < n-1; i++) {
if (s[i] == s[i+1]) {
table[i][i+1] = true;
longestBegin = i;
maxLen = 2;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i < n-len+1; i++) {
int j = i+len-1;
if (s[i] == s[j] && table[i+1][j-1]) {
table[i][j] = true;
longestBegin = i;
maxLen = len;
}
}
}
return s.substr(longestBegin, maxLen);
}