Pagini recente » Cod sursa (job #2476297) | Cod sursa (job #1672757) | Cod sursa (job #444570) | Cod sursa (job #697703) | Cod sursa (job #960286)
Cod sursa(job #960286)
#include<fstream>
#include<cstring>
#define NM 1000100
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int D[NM],i,dr,rig,lef,n,p,ii,S;
char s[NM];
int main ()
{
f>>(s+1);
n=strlen(s+1);
for(i=1;i<=n;++i)
{
if(dr>i)
{
ii=p-(i-p);
if(D[ii]/2+i<dr)
D[i]=D[ii];
else
{
lef=i-D[ii]/2;
rig=i+D[ii]/2;
if(rig>n)
rig--,lef++;
while(s[lef]==s[rig]&&lef)
{
lef--;
rig++;
}
lef++;
rig--;
D[i]=rig-lef+1;
p=i;
dr=rig;
}
}
else
{
lef=rig=i;
while(s[lef]==s[rig]&&lef)
{
lef--;
rig++;
}
lef++;
rig--;
D[i]=rig-lef+1;
p=i;
dr=rig;
}
}
for(i=1;i<=n;++i)
{
S+=(D[i]+1)/2;
D[i]=0;
}
dr=p=0;
for(i=1;i<n;++i)
{
if(dr>i)
{
ii=p-(i-p);
if(D[ii]/2+i<dr)
D[i]=D[ii];
else
{
lef=i-(D[ii]-1)/2;
rig=i+D[ii]/2;
if(rig>n)
rig--,lef++;
while(s[lef]==s[rig]&&lef)
{
lef--;
rig++;
}
lef++;
rig--;
D[i]=rig-lef+1;
p=i;
dr=rig;
}
}
else
{
lef=i;
rig=i+1;
if(s[lef]!=s[rig])
continue;
else
{
while(s[lef]==s[rig])
{
lef--;
rig++;
}
lef++;
rig--;
}
D[i]=rig-lef+1;
p=i;
dr=rig;
}
}
for(i=1;i<=n;++i)
S+=D[i]/2;
g<<S;
return 0;
}