Pagini recente » Cod sursa (job #116970) | Cod sursa (job #557038) | Cod sursa (job #1906370) | Cod sursa (job #2272995) | Cod sursa (job #928690)
Cod sursa(job #928690)
#include<fstream>
#include<string>
using namespace std;
int s[2000005],i,n,rez,a[2000005],ultim[2000005];
string sir;
int main(void){
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
fin>>sir;
n=sir.length();
for (i=0; i<n; ++i) s[2*i+1]=int(sir[i]);
s[0]=-1;
a[1]=1; a[2*n-1]=1; rez=2;
for (i=2; i<2*n-1; ++i) {
if (ultim[i]==0) {
int l=i-1,r=i+1,lung=0;
while (s[l]==s[r]) {
++lung; ultim[r]=i;
++r; --l;
}
a[i]=2*lung+1;
}
else {
int pos=i-2*(i-ultim[i]);
int brat=min(ultim[i]+a[ultim[i]]/2-i+1,a[pos]/2+1);
if (i+brat>=2*n) a[i]=2*(2*n-1-i)+1;
else {
a[i]=2*(brat-1)+1;
int l=i-brat,r=i+brat,lung=0;
while (s[l]==s[r]) {
++lung; ultim[r]=i;
++r; --l;
}
a[i]+=2*lung;
}
}
if (i%2==1) rez+=(a[i]-1)/4+1;
else { int val=(a[i]-1)/2;
if (val%2==0) rez+=val/2; else rez+=val/2+1;
}
}
fout<<rez;
return(0);
}