Pagini recente » Cod sursa (job #523870) | Cod sursa (job #1167181) | Cod sursa (job #955718) | Cod sursa (job #1138495) | Cod sursa (job #2135909)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("pscpld.in");
ofstream fo("pscpld.out");
using i64 = long long;
const int N = 1e6 + 5;
int pal[N];
char tmp[N], str[2 * N];
i64 ant;
int n, p;
int main() {
fi >> (tmp + 1);
n = strlen(tmp + 1);
for (int i = 1; i <= n; ++i) {
str[2 * i - 1] = tmp[i];
str[2 * i] = '*'; }
n = 2 * n - 1;
str[n + 1] = '\0';
str[0] = '@';
p = 1;
for (int i = 1; i <= n; ++i) {
pal[i] = max(1, min(p + pal[i] - i, pal[p - (i - p)]));
while (str[i - pal[i]] == str[i + pal[i]])
++pal[i];
if (i + pal[i] >= p + pal[p])
p = i; }
for (int i = 1; i <= n; ++i)
if (str[i] == '*')
ant+= pal[i] / 2;
else
ant+= (pal[i] + 1) / 2;
fo << ant << endl;
return 0; }