Pagini recente » Cod sursa (job #2492324) | Cod sursa (job #1282026) | Cod sursa (job #980146) | Cod sursa (job #1743479) | Cod sursa (job #2574374)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int main() {
string str; fin >> str;
int n = str.size();
vector<int> d1(n);
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 && str[i - k] == str[i + k])
k++;
d1[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
vector<int> d2(n);
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 && str[i - k - 1] == str[i + k])
k++;
d2[i] = k--;
if (i + k > r) {
l = i - k - 1;
r = i + k;
}
}
int64_t cnt = 0;
for (int i = 0; i < n; i++)
cnt += d1[i] + d2[i];
fout << cnt << '\n';
fout.close();
return 0;
}