Pagini recente » Cod sursa (job #1823578) | Cod sursa (job #417305) | Cod sursa (job #2573486) | Cod sursa (job #925304) | Cod sursa (job #3288651)
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int i,lun,mj,p[2000005],s;
string strax,st;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.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-1],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;
}