Pagini recente » Cod sursa (job #314434) | Cod sursa (job #952755) | Cod sursa (job #1500125) | Cod sursa (job #2341089) | Cod sursa (job #2517925)
#include <bits/stdc++.h>
std::ifstream input ("pscpld.in");
std::ofstream output("pscpld.out");
class ManacherCalculator {
public:
ManacherCalculator(std::string string) {
DP.resize(2*string.size() + 3);
src = string;
buildData();
runAlgorithm();
}
int even(int idx) { return DP[2*idx+2]; }
int odd (int idx) { return DP[2*idx+1]; }
private:
std::vector <int> DP;
std::string src;
std::string S;
void buildData() {
S += "$#";
for (int i=0; i<src.size(); ++i) S += src[i], S += "#";
S += "$";
}
void runAlgorithm() {
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] < src.size() && S[i+DP[i]+1] == S[i-DP[i]-1]) ++ DP[i];
if (DP[i] + i > right) center = i, right = i + DP[i];
}
}
};
int main()
{
int N;
std::string str;
input >> str;
N = str.size();
ManacherCalculator calc(str);
long long ans = 0;
for (int i=0; i<N; ++i) ans += 1ll * ((calc.odd(i)+1)/2);
for (int i=0; i<N+1; ++i) ans += 1ll * ((calc.even(i)+1)/2);
output << ans;
return 0;
}