Pagini recente » Cod sursa (job #143333) | Cod sursa (job #2158641) | Cod sursa (job #2667519) | Cod sursa (job #2392642) | Cod sursa (job #960529)
Cod sursa(job #960529)
#include<fstream>
#include<cstring>
#define NM 1000100
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]/2+i<dr)
D[i]=D[ii];
else
{
lef=i-D[ii]/2;
rig=i+D[ii]/2;
while(rig>n)
rig--,lef++;
while(s[lef]==s[rig]&&lef&&rig<=n)
{
lef--;
rig++;
}
if(s[lef]!=s[rig])
{
lef++;
rig--;
}
D[i]=rig-lef+1;
p=i;
dr=rig;
}
}
else
{
lef=rig=i;
while(s[lef]==s[rig]&&lef&&rig<=n)
{
lef--;
rig++;
}
if(s[lef]!=s[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]/2+1;
rig=i+D[ii]/2;
while(rig>n)
rig--,lef++;
while(s[lef]==s[rig]&&lef&&rig<=n)
{
lef--;
rig++;
}
if(s[lef]!=s[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<=n)
{
lef--;
rig++;
}
if(s[lef]!=s[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;
}