Pagini recente » Cod sursa (job #2598938) | Cod sursa (job #2960904) | Cod sursa (job #1397582) | Cod sursa (job #421801) | Cod sursa (job #960541)
Cod sursa(job #960541)
#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-(D[ii]-1)/2;
rig=i+(D[ii]-1)/2;
D[i]=D[ii];
lef--,rig++;
if(rig>n){
D[i]=(n-i+1)*2;continue;}
while(s[lef]==s[rig])
{
D[i]+=2;
dr=rig;
lef--;
rig++;
}
p=i;
}
}
else
{
lef=rig=i;
while(s[lef]==s[rig]&&lef&&rig<=n)
{
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);
if(D[ii]/2+i<dr)
D[i]=D[ii];
else
{
lef=i-D[ii]/2+1;
rig=i+D[ii]/2;
D[i]=D[ii];
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;
}