Pagini recente » Cod sursa (job #378007) | Cod sursa (job #1871866) | Cod sursa (job #2747719) | Cod sursa (job #620977) | Cod sursa (job #2738927)
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
void solve() {
string s;
fin >> s;
int N = s.size();
vector<int> d(N);
int64 ans = 0;
for (int i = 0, l = 0, r = -1; i < N; ++i) { /// lungimi impare
int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);
while (0 <= i - k && 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];
}
d = vector<int>(N);
for (int i = 0, l = 0, r = -1; i < N; ++i) { /// lungimi pare
int k = (i > r) ? 0 : min(d[l + r - i + 1], r - i + 1);
while (0 <= i - k - 1 && 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];
}
fout << ans << '\n';
}
void close_files() {
fin.close();
fout.close();
}
int main() {
solve();
close_files();
return 0;
}