Pagini recente » Cod sursa (job #2252608) | Cod sursa (job #444214) | Cod sursa (job #457780) | Cod sursa (job #593156) | Cod sursa (job #2232037)
#include <fstream>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int d1[1000005];
int d2[1000005];
char s[1000005];
int main() {
ios::sync_with_stdio(false);
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
cin >> s;
int n = strlen(s);
int k;
long long res = 0;
for (int i = 0, l = 0, r = -1; i < n; ++i) {
d1[i] = (i > r) ? 1 : min(d1[l + r - i], r - i);
while (0 <= i - d1[i] && i + d1[i] < n && s[i - d1[i]] == s[i + d1[i]])
++d1[i];
k = d1[i] - 1;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
for (int i = 0, l = 0, r = -1; i < n; ++i) {
d2[i] = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
while (0 <= i - d2[i] - 1 && i + d2[i] < n && s[i - d2[i] - 1] == s[i + d2[i]])
++d2[i];
k = d2[i] - 1;
if (i + k > r) {
l = i - k - 1;
r = i + k;
}
res += d1[i] + d2[i];
}
cout << res;
return 0;
}