Pagini recente » Cod sursa (job #122965) | Cod sursa (job #1599261) | Cod sursa (job #693535) | Cod sursa (job #1230581) | Cod sursa (job #2068926)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LMAX 1000005
using namespace std;
char s[LMAX];
long long counter = 0;
int Lp[2*LMAX + 1];
void MaicaTa()
{
int len = strlen(s);
if(len == 0)
return;
len = 2 * len + 1;
Lp[0] = 0;
Lp[1] = 1;
int C = 1, R = 2;
int iMirror;
int expand = 0;
int diff = -1;
for(int i = 2; i < len; i++)
{
iMirror = 2 * C - 1;
expand = 0;
diff = R - i;
if (diff > 0)
{
if(diff > 0)
Lp[i] = min(Lp[iMirror], diff);
while ( ((i + Lp[i]) < len && (i - Lp[i]) > 0) && ( ((i + Lp[i] + 1) % 2 == 0) || (s[(i + Lp[i] + 1)/2] == s[(i - Lp[i] - 1)/2] )))
{
Lp[i]++;
}
}
if (i + Lp[i] > R)
{
C = i;
R = i + Lp[i];
}
}
for(int i = 1; i < len; i++)
if(Lp[i] %2 == 0)
counter += Lp[i] / 2;
else
counter += (Lp[i] / 2 + 1);
}
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
scanf("%s", s);
MaicaTa();
printf("%lld", counter);
return 0;
}