Pagini recente » Cod sursa (job #2518298) | Cod sursa (job #1407316) | Cod sursa (job #1400393) | Cod sursa (job #1441991) | Cod sursa (job #1227505)
#include <cstdio>
#include <string>
#define MaxN 1000005
#define infile "pscpld.in"
#define outfile "pscpld.out"
long long N, sol[MaxN], solp[MaxN], rez;
char a[MaxN];
void read()
{
int i;
scanf("%s", &a);
N = strlen(a);
for (i = N; i >= 1; i--)
a[i] = a[i - 1];
}
long long minim(long long x, long long y)
{
if (x<y)
return x;
return y;
}
void solvei()
{
long long last = 1, l, i;
for (i = 2; i<N; i++)
{
if (i<last + sol[last])
sol[i] = minim(sol[last - (i - last)], last + sol[last] - i);
l = sol[i];
if (last + sol[last] <= i + sol[i])
{
last = i;
while (i - l >= 1 && i + l <= N && a[i - l] == a[i + l])
l++;
if (l >= 1)
sol[i] = l - 1;
}
rez += sol[i];
}
}
void solvep()
{
long long last = 1, l, i;
if (a[1] == a[2])
solp[1] = 1;
for (i = 2; i<N; i++)
{
if (i<last + solp[last])
solp[i] = minim(solp[last - (i - last)], last + solp[last] - i);
l = solp[i];
if (last + solp[last] <= i + solp[i])
{
last = i;
while (i - l >= 1 && i + l + 1 <= N && a[i - l] == a[i + l + 1])
l++;
if (l >= 1)
solp[i] = l - 1;
}
rez += solp[i];
}
for (i = 1; i<N; i++)
if (a[i] == a[i + 1])
solp[i]++, rez++;
}
void write()
{
rez += N;
printf("%lld\n", rez);
}
int main()
{
freopen(infile, "r", stdin);
freopen(outfile, "w", stdout);
read();
solvei();
solvep();
write();
fclose(stdin);
fclose(stdout);
return 0;
}