Pagini recente » Cod sursa (job #288744) | Cod sursa (job #3151343) | Cod sursa (job #2055931) | Cod sursa (job #1683994) | Cod sursa (job #2068868)
#include <cstdio>
#include <cstring>
#define LMAX 1000005
using namespace std;
char s[LMAX];
long long counter = 0;
void MaicaTa()
{
int len = strlen(s);
if(len == 0)
return;
len = 2 * len + 1;
int Lp[len];
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;
exp = 0;
diff = R - i;
if (diff > 0)
{
if(Lp[iMirror] < diff)
Lp[i] = Lp[iMirror];
else
if(Lp[iMirror] == diff && i == len - 1)
Lp[i] = Lp[iMirror];
else
if(Lp[iMirror] == diff && i < len - 1)
{
Lp[i] = Lp[iMirror];
expand = 1;
}
else
if(Lp[iMirror] > diff)
{
Lp[i] = diff;
expand = 1;
}
}
else
{
Lp[i] = 0;
expand = 1;
}
if(expand == 1)
{
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]++;
}
}
}
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;
}