Pagini recente » Cod sursa (job #2655009) | Cod sursa (job #755439) | Cod sursa (job #673450) | Cod sursa (job #1715263) | Cod sursa (job #2810143)
#include <bits/stdc++.h>
using namespace std;
inline void Open(const string Name) {
#ifndef ONLINE_JUDGE
(void)!freopen((Name + ".in").c_str(), "r", stdin);
(void)!freopen((Name + ".out").c_str(), "w", stdout);
#endif
}
char s[1000001];
int d1[1000001], d2[1000001];
int n;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
Open("pscpld");
cin >> s;
n = strlen(s);
for(int i = 0, l = 0, r = -1;i < n;i++) {
int k = (i > r)? 1 : min(d1[l + r - i], r - i + 1);
while(0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
k++;
}
d1[i] = k--;
if(i + k > r) {
l = i - k;
r = i + k;
}
}
for(int i = 0, l = 0, r = -1;i < n;i++) {
int k = (i > r)? 0 : min(d2[l + r - i + 1], r - i + 1);
while(0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
k++;
}
d2[i] = k--;
if(i + k > r) {
l = i - k - 1;
r = i + k;
}
}
int ans = 0;
for(int i = 0;i < n;i++)
ans += d1[i] + d2[i];
cout << ans;
return 0;
}