Pagini recente » Cod sursa (job #712456) | Cod sursa (job #2262960) | Cod sursa (job #1895850) | Cod sursa (job #1370990) | Cod sursa (job #2715730)
#include <fstream>
#include <string>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
const int NMAX = 1e6;
string s;
int manacher[2 * NMAX + 5];
long long ans;
void Manacher() {
int drMax = -1, posDrMax = -1;
for(int i = 0; i < (int)s.size(); i++) {
if(i > drMax) {
int st = i - 1, dr = i + 1;
while(st >= 0 && dr < (int)s.size() && s[st] == s[dr]) {
st--, dr++;
}
st++, dr--;
manacher[i] = dr - i;
drMax = dr;
posDrMax = i;
} else {
if(i + manacher[2 * posDrMax - i] < drMax) {
manacher[i] = manacher[2 * posDrMax - i];
} else {
int st = 2 * i - drMax - 1, dr = drMax + 1;
while(st >= 0 && dr < (int)s.size() && s[st] == s[dr]) {
st--, dr++;
}
st++, dr--;
manacher[i] = dr - i;
drMax = dr;
posDrMax = i;
}
}
}
for(int i = 0; i < (int)s.size(); i++) {
if(i % 2 == 0) {
///'*'
ans += (manacher[i] + 1) / 2;
} else {
///'a'-'z'
ans += (manacher[i] + 2) / 2;
}
}
}
int main() {
string aux;
cin >> aux;
s += '*';
for(char c : aux) {
s += c;
s += '*';
}
Manacher();
cout << ans << '\n';
return 0;
}