Pagini recente » Cod sursa (job #2389460) | Cod sursa (job #2475945) | Cod sursa (job #2941864) | Cod sursa (job #1259836) | Cod sursa (job #2799136)
#include <fstream>
#include <cstring>
using namespace std;
const int N = 1e6 + 5;
char s[N];
int d[N], n;
long long ans;
void mnc() {
int l, r;
l = 0, r = -1;
for (int i = 0; i < n; ++i) {
int k;
if (i > r) k = 1;
else k = min(d[l + r - i], r - i + 1);
while (i - k >= 0 && i + k < n && s[i - k] == s[i + k])
++k;
d[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
ans += d[i];
}
l = 0, r = -1;
for (int i = 0; i < n; ++i) {
int k;
if (i > r) k = 0;
else k = min(d[l + r - i + 1], r - i + 1);
while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k])
++k;
d[i] = k--;
if (i + k > r) {
l = i - k - 1;
r = i + k;
}
ans += d[i];
}
}
int main() {
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
cin >> s;
n = strlen(s);
cin.close();
mnc();
cout << ans << "\n";
cout.close();
return 0;
}