Pagini recente » Cod sursa (job #641712) | Cod sursa (job #27893) | Cod sursa (job #2594522) | Cod sursa (job #1704816) | Cod sursa (job #3268913)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
const char BOGUS = '*';
string withBogus(const string& s) {
const int n = s.length();
// Construct string of size n filled with null characters
// Predefined sizes are usually faster, because they don't require
// more allocations.
string sp(2 * n - 1, '\0');
for (int i = 0; i < n; i++) {
sp[2 * i] = s[i];
if (i < n - 1) {
sp[2 * i + 1] = BOGUS;
}
}
return sp;
}
void extendRadius(const string& sp, int center, int& radius) {
while (center - (radius + 1) >= 0 &&
center + (radius + 1) >= 0 &&
sp[center - (radius + 1)] == sp[center + (radius + 1)]) {
radius++;
}
}
vector<int> computePalindromeRadii(const string& sp) {
const int n = sp.length();
vector<int> result(n);
int center = 0, radius = 0;
int oldCenter, oldRadius;
while (center < n) {
extendRadius(sp, center, radius);
result[center] = radius;
oldCenter = center;
oldRadius = radius;
center++;
radius = 0;
while (center <= oldCenter + oldRadius) {
/*
* We have this example "abcacbad" -> "a*b*c*a*c*b*a*d" after adding
* bogus characters.
* _
* ||a * b * c *|a|* c * b * a | * d
* || ^ | | ____ └-|---oldCenter + oldRadius
* ||<-┬---->| | └-|center||
* | | | └-oldCenter |
* | | ┌--┘ |
* | └--|-maxMirroredRadius |
* | └--┐ |
* | | |
* | | |
* | mirroredCenter |
* | |
* |<-- old sequence -->|
*/
const int mirroredCenter = oldCenter - (center - oldCenter);
const int maxMirroredRadius = oldCenter + oldRadius - center;
if (result[mirroredCenter] != maxMirroredRadius) {
result[center] = min(result[mirroredCenter], maxMirroredRadius);
center++;
} else if (result[mirroredCenter] == maxMirroredRadius) {
result[center] = maxMirroredRadius;
radius = maxMirroredRadius;
break;
}
}
}
return result;
}
int64_t computeResult(const string& s) {
string sp = withBogus(s);
const int n = sp.length();
auto radii = computePalindromeRadii(sp);
int64_t result = 0;
for (int i = 0; i < n; i++) {
/* result[i] is the radius, where we remove the bogus chars,
* so (result[i] / 2) for the real radius ->
* -> real radius * 2 = length
*
* special case for even length palindromic sequences ->
* -> we remove the bogus character from the middle;
*/
int length;
const bool isOddLength = i % 2 == 0;
if (isOddLength) {
length = (radii[i] / 2 * 2) + 1;
} else {
length = radii[i] + 1;
}
result += length / 2 + isOddLength;
}
return result;
}
int main() {
ifstream f("pscpld.in");
ofstream g("pscpld.out");
string s;
f >> s;
g << computeResult(s) << std::endl;
return 0;
}