Cod sursa(job #680491)

Utilizator feelshiftFeelshift feelshift Data 15 februarie 2012 18:06:12
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
// http://infoarena.ro/problema/pscpld
#include <fstream>
#include <string>
using namespace std;

ifstream in("pscpld.in");
ofstream out("pscpld.out");

const int MAXSIZE = 20000;

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);
}