Pagini recente » Cod sursa (job #315838) | Cod sursa (job #2359466) | Cod sursa (job #2208003) | Cod sursa (job #1801383) | Cod sursa (job #1881615)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char s[1000001];
int LPS[2000002];
int c, r, n;
int k;
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf("%s",s);
n=2*strlen(s)+1;
LPS[0]=0;
LPS[1]=1;
c=1;
r=2;
for(int i=2;i<=n;i++)
{
int mirror = 2*c - i;
bool expand = 0;
if(r<=i)
{
LPS[i]=0;
expand = 1;
}
else
{
if(LPS[mirror] < r-i)
{
LPS[i]=LPS[mirror];
}
else
{
LPS[i] = min(LPS[mirror],r-i);
expand = 1;
}
}
if(expand)
{
while(i-LPS[i]>0 && i+LPS[i]<n)
{
if((i-LPS[i]-1)%2==0)
LPS[i]++;
else
{
if(s[(i-LPS[i]-1)/2]==s[(i+LPS[i]+1)/2])
LPS[i]++;
else break;
}
}
if(i+LPS[i] > r)
{
r = i+LPS[i];
c=i;
}
}
}
for(int i=0;i<n;i++)
{
if(LPS[i]%2==0)
k+=LPS[i]/2;
else k+=LPS[i]/2+1;
}
printf("%d",k);
return 0;
}