Pagini recente » Cod sursa (job #3272242) | Cod sursa (job #555162) | Cod sursa (job #187362) | Cod sursa (job #3040319) | Cod sursa (job #479372)
Cod sursa(job #479372)
#include <cstdio>
#include <string>
#define MaxN 1000005
#define infile "pscpld.in"
#define outfile "pscpld.out"
long long N,sol[MaxN],solp[MaxN],rez;
char a[MaxN];
void read()
{
int i;
scanf("%s",&a);
N=strlen(a);
for(i=N;i>=1;i--)
a[i]=a[i-1];
}
long long minim(long long x,long long y)
{
if(x<y)
return x;
return y;
}
void solve()
{
long long lasti,lastp,l,i;
lasti=lastp=1;
if(a[1]==a[2])
solp[1]=1;
for(i=2;i<N;i++)
{
if(a[i-1]==a[i])
rez++;
if(i<lasti+sol[lasti])
sol[i]=minim(sol[lasti-(i-lasti)],lasti+sol[lasti]-i);
l=sol[i];
if(lasti+sol[lasti]<=i+sol[i])
{
lasti=i;
while(i-l>=1 && i+l<=N && a[i-l]==a[i+l])
l++;
if(l>=1)
sol[i]=l-1;
}
rez+=sol[i];
//
if(i<lastp+solp[lastp])
solp[i]=minim(solp[lastp-(i-lastp)], lastp+solp[lastp]-i);
l=solp[i];
if(lastp+solp[lastp]<=i+solp[i])
{
lastp=i;
while(i-l>=1 && i+l+1<=N && a[i-l]==a[i+l+1])
l++;
if(l>=1)
solp[i]=l-1;
}
rez+=solp[i];
}
}
/*void solvei()
{
long long last=1,l,i;
for(i=2;i<N;i++)
{
if(i<last+sol[last])
sol[i]=minim(sol[last-(i-last)], last+sol[last]-i);
l=sol[i];
if(last+sol[last]<=i+sol[i])
{
last=i;
while(i-l>=1 && i+l<=N && a[i-l]==a[i+l])
l++;
if(l>=1)
sol[i]=l-1;
}
rez+=sol[i];
}
}
void solvep()
{
long long last=1,l,i;
if(a[1]==a[2])
solp[1]=1, rez++;
for(i=2;i<N;i++)
{
if(i<last+solp[last])
solp[i]=minim(solp[last-(i-last)], last+solp[last]-i);
l=solp[i];
if(last+solp[last]<=i+solp[i])
{
last=i;
while(i-l>=1 && i+l+1<=N && a[i-l]==a[i+l+1])
l++;
if(l>=1)
solp[i]=l-1;
}
rez+=solp[i];
}
for(i=1;i<N;i++)
if(a[i]==a[i+1])
solp[i]++, rez++;
}*/
void write()
{
rez+=N;
printf("%lld\n",rez);
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
/*solvei();
solvep();*/
solve();
write();
fclose(stdin);
fclose(stdout);
return 0;
}