Pagini recente » Cod sursa (job #2450547) | Cod sursa (job #342802) | Cod sursa (job #1235657) | Cod sursa (job #2465435) | Cod sursa (job #1132984)
#include<cstdio>
#include<cstring>
using namespace std;
int 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);
nr=n;
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--;
y++;
dp[i]++;
nr++;
}
else break;
}
if(r<dp[i]+i-1)
{
r=dp[i]+i-1;
j=i;
}
//printf("%d ",dp[i]);
}
for(i=1;i<=n;i++)
{
dp[i]=1;
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--;
y++;
dp[i]++;
nr++;
}
else break;
}
if(r<dp[i]+i)
{
r=dp[i]+i;
j=i;
}
//printf("%d ",dp[i]);
}
printf("%d",nr);
return 0;
}