Pagini recente » Cod sursa (job #2370550) | Cod sursa (job #2770235) | Cod sursa (job #1530690) | Cod sursa (job #2873562) | Cod sursa (job #2289981)
#include <bits/stdc++.h>
#define ll long long
#define maxN 1000000
using namespace std;
FILE *fin = freopen("pscpld.in", "r", stdin);
FILE *fout = freopen("pscpld.out", "w", stdout);
char s[maxN + 1];
class String
{
public :
int n, *p;
char *Q;
String(int n)
{
this->n = n;
p = new int[2 * n + 2];
Q = new char[2 * n + 2];
Q[2 * n + 1] = '$';
for (int i = 0; i <= 2 * n + 1; ++ i)
p[i] = 0;
for (int i = 0; i <= 2 * n; ++ i)
if (i & 1)
Q[i] = s[i / 2];
else
Q[i] = '#';
}
void compP();
};
ll ans;
void String::compP()
{
int N = 2 * n + 1;
int c = 0, r = 0;
for (int i = 1; i < N; ++ i)
{
int iMirror = 2 * c - i;
if (r > i)
p[i] = min(p[iMirror], r - i);
while (i - p[i] - 1 >= 0 && Q[i + p[i] + 1] == Q[i - p[i] - 1])
++ p[i];
if (p[i] + i > r)
{
c = i;
r = i + p[i];
}
ans += ((p[i] + 1) / 2);
}
}
int main()
{
scanf("%s", &s);
int n = strlen(s);
String S(n);
S.compP();
printf("%lld\n", ans);
return 0;
}