Pagini recente » Cod sursa (job #1442834) | Cod sursa (job #1873693) | Cod sursa (job #2438337) | Cod sursa (job #2352198) | Cod sursa (job #1140052)
#include<cstdio>
#include<cstring>
using namespace std;
long long r,j,min,nr,n,x,y,i,dp[1000009];
char s[1000009];
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
gets(s+1);
n=strlen(s+1);
for(i=1;i<=n;i++)
{
dp[i]=1;
if(r>=i)
{
min=dp[j-(i-j)];
if(min>r-i+1) min=r-i+1;
dp[i]=min;
}
x=i-dp[i];
y=i+dp[i];
while(1)
{
if(s[x]==s[y]&&x>0&&y<=n)
{
x--;
y++;
dp[i]++;
}
else break;
}
if(r<dp[i]+i-1)
{
r=dp[i]+i-1;
j=i;
}
nr+=dp[i];
}
r=j=0;
for(i=1;i<=n;i++)
{
dp[i]=0;
if(r>=i)
{
min=dp[j-(i-j)];
if(min>r-i) min=r-i;
dp[i]=min;
}
x=i-dp[i]-1;
y=i+dp[i];
while(1)
{
if(s[x]==s[y]&&x>0&&y<=n)
{
x--;
y++;
dp[i]++;
}
else break;
}
if(r<dp[i]+i)
{
r=dp[i]+i;
j=i;
}
nr+=dp[i];
}
printf("%lld",nr);
return 0;
}