Cod sursa(job #960527)
Utilizator | Data | 10 iunie 2013 17:42:51 | |
---|---|---|---|
Problema | PScPld | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.45 kb |
#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);
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;
}