Pagini recente » Cod sursa (job #2410942) | Cod sursa (job #2087318) | Cod sursa (job #1840660) | Cod sursa (job #1757881) | Cod sursa (job #2442528)
#include <bits/stdc++.h>
using namespace std;
char c[2000005];
int mx[2000005];
int main()
{
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int n,dr=0,st=0;
string s;
cin>>s;
n=s.size();
for(int i=0;i<n;i++)
{
c[2*i+1]=s[i];
c[2*(i+1)]='*';
}
c[0]='*';
n*=2;
for(int i=1;i<=2*n;i++)
{
if(i<=dr)
{
int o=st+dr-i;
mx[i]=min(mx[o],o-st+1);
int jdr=i+mx[i],jst=i-mx[i];
while(jst>=0 and jdr<=n and c[jdr]==c[jst])
{
jdr++;
jst--;
mx[i]++;
}
if(dr<i+mx[i]-1)
{
dr=i+mx[i]-1;
st=i-mx[i]+1;
}
}
else
{
int jdr=i,jst=i;
while(jst>=0 and jdr<=n and c[jdr]==c[jst])
{
jdr++;
jst--;
mx[i]++;
}
dr=i+mx[i]-1;
st=i-mx[i]+1;
}
}
long long sum=0;
for(int i=1;i<=n;i++)
sum+=(long long)mx[i]/2;
cout<<sum;
return 0;
}