Pagini recente » Cod sursa (job #1944417) | Cod sursa (job #867222) | Cod sursa (job #2526815) | Cod sursa (job #2196217) | Cod sursa (job #1226785)
#include<fstream>
using namespace std;
char v[1000100],s[2000100];
int n,i,st,dr,poz,len[2000100];
long long sol;
int main()
{
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
fin>>v;
n=0;
s[++n]='*';
for(i=0;v[i]!=0;i++)
{
s[++n]=v[i];
s[++n]='*';
}
st=1;
dr=3;
len[2]=1;
for(i=3;i<=n;i++)
{
if(i>dr)
{
st=dr=i;
while(st>1 && dr<n && s[st-1]==s[dr+1])
{
len[i]++;
st--;
dr++;
}
}
else
{
poz=st+(dr-i);
if(i+len[poz]<dr)
len[i]=len[poz];
else
{
len[i]=dr-i;
st=i-len[i];
dr=i+len[i];
while(st>1 && dr<n && s[st-1]==s[dr+1])
{
len[i]++;
st--;
dr++;
}
}
}
}
for(i=1;i<=n;i++)
sol+=(long long)((len[i]+1)/2);
fout<<sol<<"\n";
return 0;
}