Pagini recente » Cod sursa (job #2469050) | Cod sursa (job #1128912) | Cod sursa (job #1010636) | Cod sursa (job #2175980) | Cod sursa (job #2719272)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int manacher[2000005];
int main()
{
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string s, source = "&";
int cnt = 0, a = 0, n;
fin >> s;
n = s.size() * 2 + 1;
for (int i = 1; i <= n; ++i) {
if (i % 2 != 0) {
source += "$";
} else {
source += s.at(a);
a += 1;
}
}
int j = -1, pal_j = -1;
for (int i = 1; i <= n; ++i) {
manacher[i] = 1;
}
for (int i = 1; i <= n; ++i) {
if (i > j + (pal_j - 1) / 2) {
int m = i + 1;
while (source[m] == source[2 * i - m]) {
manacher[i] += 2;
m += 1;
}
if (manacher[i] > pal_j) {
pal_j = manacher[i];
j = i;
}
} else if (i + (manacher[2 * j - i] - 1) / 2 < j + (pal_j - 1) / 2) {
manacher[i] = manacher[2 * j - i];
} else {
manacher[i] = manacher[2 * j - i];
int x = (manacher[i] - 1) / 2;
int p = i + x + 1;
while (source[p] == source[2 * i - p]) {
manacher[i] += 2;
p += 1;
}
if (manacher[i] > pal_j) {
pal_j = manacher[i];
j = i;
}
}
}
long long ans = 0;
for (int i = 1; i <= n; ++i) {
ans += (manacher[i] / 2 + 1) / 2;
}
fout << ans;
return 0;
}