Cod sursa(job #681461)

Utilizator feelshiftFeelshift feelshift Data 17 februarie 2012 08:36:32
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 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;
int best[2*MAXSIZE+1];
string text;

int subsequences(int center);

string preProcess(string s);
string longestPalindrome(string s);

int main() {
	in >> text;

	//out << text;

	size = text.length() - 1;

	for(int i=0;i<=size;i++)
		answer += subsequences(i);

	//out << longestPalindrome(text);
	out << answer << "\n";

	return (0);
}

int subsequences(int center) {
	int left = 0;
	int right = 0;
	int oddLength = 0;
	int evenLength = 0;

	left = right = center;
	while(0 <= left && right <= size && text[left--] == text[right++])
		oddLength++;

	left = center;
	right = center + 1;
	while(0 <= left && right <= size && text[left--] == text[right++])
		evenLength++;

	return (oddLength + evenLength);
}

// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
string preProcess(string s) {
  int n = s.length();
  if (n == 0) return "^$";
  string ret = "^";
  for (int i = 0; i < n; i++)
    ret += "#" + s.substr(i, 1);

  ret += "#$";
  return ret;
}

string longestPalindrome(string s) {
  string T = preProcess(s);
  int n = T.length();
  int *P = new int[n];
  int C = 0, R = 0;
  for (int i = 1; i < n-1; i++) {
    int i_mirror = 2*C-i; // equals to i' = C - (i-C)

    P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;

    // Attempt to expand palindrome centered at i
    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
      P[i]++;

    // If palindrome centered at i expand past R,
    // adjust center based on expanded palindrome.
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }

  // Find the maximum element in P.
  int maxLen = 0;
  int centerIndex = 0;
  for (int i = 1; i < n-1; i++) {
  	answer += P[i];
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  delete[] P;

  return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
}