Pagini recente » Cod sursa (job #1173308) | Cod sursa (job #2642608) | Cod sursa (job #2818233) | Cod sursa (job #1913692) | Cod sursa (job #681461)
Cod sursa(job #681461)
// 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);
}