Pagini recente » Cod sursa (job #1489844) | Cod sursa (job #2321964) | Cod sursa (job #1626794) | Cod sursa (job #1082767) | Cod sursa (job #960557)
Cod sursa(job #960557)
#include<fstream>
#include<cstring>
#define NM 10000100
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
long long D[NM],i,dr,rig,lef,n,p,ii;
long long S;
char s[NM];
int main ()
{
f>>(s+1);
n=strlen(s+1);
s[0]='!';
for(i=1;i<=n;++i)
{
if(dr>i)
{
ii=p-(i-p);
if((D[ii]-1)/2+i<dr)
D[i]=D[ii];
else
{
lef=i-(dr-i);
rig=dr;
D[i]=(rig-i+1)*2;
lef--,rig++;
while(s[lef]==s[rig])
{
D[i]+=2;
dr=rig;
lef--;
rig++;
}
p=i;
}
}
else
{
lef=rig=i;
while(s[lef]==s[rig])
{
D[i]+=2;
dr=rig;
lef--;
rig++;
}
p=i;
}
}
for(i=1;i<=n;++i)
{
S+=D[i]/2;
D[i]=0;
}
dr=p=0;
for(i=1;i<n;++i)
{
if(dr>i)
{
ii=p-(i-p)-1;
if(D[ii]/2+i-1<dr)
D[i]=D[ii];
else
{
lef=i-(dr-i)+1;
rig=dr;
D[i]=(rig-i+1)*2;
lef--;
rig++;
if(rig>n){
D[i]=(n-i)*2;p=i;dr=n;continue;}
while(s[lef]==s[rig])
{
D[i]+=2;
dr=rig;
lef--;
rig++;
}
p=i;
}
}
else
{
lef=i;
rig=i+1;
if(s[lef]!=s[rig])
continue;
else
while(s[lef]==s[rig])
{
D[i]+=2;
dr=rig;
lef--;
rig++;
}
p=i;
}
}
for(i=1;i<n;++i)
S+=D[i]/2;
g<<S<<"\n";
return 0;
}