Pagini recente » Cod sursa (job #433487) | Cod sursa (job #2713600) | Cod sursa (job #656296) | Cod sursa (job #1214674) | Cod sursa (job #680494)
Cod sursa(job #680494)
// 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[MAXSIZE][MAXSIZE];
string text;
bool palindrom(int i,int k);
string longestPalindromeDP(string s);
int main() {
in >> text;
//out << text;
size = text.length() - 1;
//out << longestPalindromeDP(text);
for(int i=0;i<=size;i++)
best[i][i] = true;
for(int i=0;i<=size;i++)
for(int k=1;k<=size-i;k++) {
int s = i + k;
best[k][s] = palindrom(k,s);
answer += best[k][s];
}
/*for(int i=0;i<=size;i++) {
for(int k=0;k<=size;k++)
out << best[i][k] << " ";
out << "\n";
}*/
out << answer + 1 << "\n";
return (0);
}
bool palindrom(int i,int k) {
if(i == k || k == i + 1)
return best[i][k];
else
if(text[i] == text[k] && best[i+1][k-1])
return true;
else
return palindrom(i+1,k-1);
}
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);
}