Pagini recente » Cod sursa (job #114139) | Cod sursa (job #2438357) | Cod sursa (job #3214647) | Cod sursa (job #430862) | Cod sursa (job #2376835)
#include <bits/stdc++.h>
#define llg long long
#define MAXN 1000005
int N, DP[2*MAXN];
std::string S, Input;
void Manacher() {
int Center = 0, Right = 0, mirror;
for (int i=1; i<S.size()-1; ++i) {
mirror = 2*Center - i;
if (i < Right)
DP[i] = std::min(DP[mirror], Right - i);
while (DP[i] < N && S[i+DP[i]+1] == S[i-DP[i]-1])
++ DP[i];
if (DP[i] + i > Right)
Center = i, Right = i + DP[i];
}
}
std::ifstream In ("pscpld.in");
std::ofstream Out("pscpld.out");
void Citire() {
In >> Input;
N = Input.size();
S += "$#";
for (int i=0; i<N; ++i)
S += Input[i], S += "#";
S += "$";
}
void Rezolvare() {
Manacher();
llg Ans = 0;
for (int i=1; i<S.size(); ++i)
Ans += 1LL * (DP[i] / 2 + (DP[i]&1));
Out << Ans << '\n';
}
int main()
{
Citire();
Rezolvare();
return 0;
}