Cod sursa(job #680521)

Utilizator feelshiftFeelshift feelshift Data 15 februarie 2012 18:42:03
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
// 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);
}