Pagini recente » Cod sursa (job #2288913) | Cod sursa (job #2366880)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 10;
#ifndef BLAT
ifstream f("pscpld.in");
ofstream g("pscpld.out");
#endif
int dp[MAXN];
int main() {
#ifdef BLAT
freopen("input", "r", stdin);
#define f cin
#define g cout
#endif
ios::sync_with_stdio(false);
f.tie(0);
g.tie(0);
string m;
f >> m;
string s = "#";
for(auto &x : m) s = s + x + '#';
long long ans = 0;
for(int i = 0, l = 0, r = -1; i < s.size(); ++i) {
int k = (i > r) ? 1 : min(r - i, dp[l + r - i]);
while(i - k >= 0 && i + k < s.size() && s[i-k] == s[i+k]) ++k;
dp[i] = k--;
ans += (dp[i])/2;
if(i + k > r) {
r = i + k;
l = i - k;
}
}
g << ans << '\n';
return 0;
}