Pagini recente » Cod sursa (job #2653031) | Cod sursa (job #1494561) | Cod sursa (job #2764582) | Cod sursa (job #2851100) | Cod sursa (job #2539229)
#include <fstream>
#include <iostream>
#define NMAX 2 * 1000000 + 5
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string strR, str = "";
int N;
long long L[NMAX];
void read() {
fin >> strR;
for (int i = 0; i < strR.length(); ++i) {
str += "!!";
str[2 * i + 1] = strR[i];
}
str += "!";
N = str.length();
}
void manacher() {
int right = 2, center = 1, simi;
long long dist;
bool expand;
L[0] = L[N] = 0;
L[1] = 1;
for (int i = 2; i <= N; ++i) {
simi = 2 * center - i;
bool expand = false;
dist = right - i;
if (dist >= 0) {
if (L[simi] < dist || i == N - 1) {
L[i] = L[simi];
}
else {
L[i] = min(L[simi], dist);
expand = true;
}
}
else {
L[i] = 0;
expand = true;
}
if (expand) {
while ((i + L[i]) < N && (i - L[i]) > 0 && str[i + L[i] + 1] == str[i - L[i] - 1]) {
L[i]++;
}
}
if (i + L[i] > right) {
center = i;
right = i + L[i];
}
}
}
int main()
{
read();
manacher();
long long sum = 0;
for (int i = 0; i < N; ++i) {
sum += (L[i] / 2);
if (i & 1) {
sum++;
}
}
fout << sum << "\n";
return 0;
}