Pagini recente » Cod sursa (job #1031311) | Cod sursa (job #67980) | Cod sursa (job #42142) | Cod sursa (job #303648) | Cod sursa (job #3288654)
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int i,lun,mj,p[2000005];
long long s;
string strax,st;
int main()
{
ios_base::sync_with_stdio(false);
in.tie(0);
out.tie(0);
in>>strax;
st="**",lun=2;
for(i=0;strax[i];++i)
st+=strax[i],st+='*',lun+=2;
mj=0;
for(i=1;i<=lun;++i)
{
if(mj+p[mj]>=i)
{
p[i]=min(p[2*mj-i],mj+p[mj]-i);
while(i+1+p[i]<=lun && i-1-p[i]>=1 && st[i+1+p[i]]==st[i-1-p[i]])
++p[i];
if(i+p[i]>=mj+p[mj])
mj=i;
}
else
{
p[i]=0;
while(i+1+p[i]<=lun && i-1-p[i]>=1 && st[i+1+p[i]]==st[i-1-p[i]])
++p[i];
mj=i;
}
}
for(i=1;i<=lun;++i)
s+=(p[i]+1)>>1;
out<<s;
return 0;
}