Pagini recente » Cod sursa (job #3360917) | Cod sursa (job #3359616) | Cod sursa (job #3359708) | Cod sursa (job #3358978) | Cod sursa (job #3359518)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string s;
vector<int> d1, d2;
long long ans;
int main() {
fin >> s;
int n = s.size();
d1.resize(n);
d2.resize(n);
for (int i = 0, l = 0, r = -1; i < n; ++i) {
int k = 1;
if (i <= r)
k = min(d1[l + r - i], r - i + 1);
while (i - k >= 0 && i + k < n && s[i - k] == s[i + k])
++k;
d1[i] = k;
if (i + k - 1 > r) {
l = i - k + 1;
r = i + k - 1;
}
}
for (int i = 0, l = 0, r = -1; i < n; ++i) {
int k = 0;
if (i <= r)
k = min(d2[l + r - i + 1], r - i + 1);
while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k])
++k;
d2[i] = k;
if (i + k - 1 > r) {
l = i - k;
r = i + k - 1;
}
}
for (int i = 0; i < n; ++i)
ans += d1[i] + d2[i];
fout << ans << "\n";
return 0;
}