Pagini recente » Cod sursa (job #3346588) | Cod sursa (job #3317717) | Cod sursa (job #3349687) | Cod sursa (job #3332678) | Cod sursa (job #3332236)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
string s;
cin >> s;
int n = s.size();
string t = "@";
for (char c : s) {
t += "#";
t += c;
}
t += "#$";
int m = t.size();
vector<int> p(m, 0);
int center = 0, right = 0;
long long total = 0;
for (int i = 1; i < m - 1; i++) {
int mirror = 2 * center - i;
if (i < right)
p[i] = min(right - i, p[mirror]);
while (t[i + (1 + p[i])] == t[i - (1 + p[i])])
p[i]++;
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
total += (p[i] + 1) / 2;
}
cout << total << "\n";
return 0;
}