Pagini recente » Cod sursa (job #1793964) | Monitorul de evaluare | Istoria paginii utilizator/bibsis | Statistici Adriana (AdrianaH) | Cod sursa (job #1528664)
#include <cstdio>
#include <cstring>
using namespace std;
int n,poz,i,p,ok,nr,dp[1000003];
char s[1000003];
int minim(int xx, int yy)
{
if(xx<yy)return xx;
return yy;
}
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++)
{
if(poz>=i)dp[i]=minim(poz-i+1,dp[p-(i-p)]);
else dp[i]=1;
while(s[i+dp[i]]==s[i-dp[i]]&&i+dp[i]<=n&&i-dp[i]>0)
{
dp[i]++;
}
nr=nr+dp[i];
if(i+dp[i]-1>poz)
{
p=i;
poz=i+dp[i]-1;
}
}
p=poz=0;
for(i=1;i<=n;i++)
dp[i]=0;
for(i=2;i<=n;i++)
{
if(poz>=i)dp[i]=minim(poz-i+1,dp[p-(i-p)]);
while(s[i+dp[i]]==s[i-dp[i]-1]&&i+dp[i]<=n&&i-dp[i]>0)
{
dp[i]++;
}
nr=nr+dp[i];
if(i+dp[i]-1>poz)
{
p=i;
poz=i+dp[i]-1;
}
}
printf("%d",nr);
return 0;
}