Pagini recente » Cod sursa (job #30965) | Cod sursa (job #2129412) | Monitorul de evaluare | Cod sursa (job #2369288) | Cod sursa (job #929017)
Cod sursa(job #929017)
#include<fstream>
#include<string>
using namespace std;
int i,n,rez,a[2000005],u,lim;
string sir;
char s[2000005];
int main(void){
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
getline(fin,sir);
n=sir.length();
for (i=0; i<n; ++i){ s[2*i+1]=sir[i]; s[2*i]='.'; }
s[0]='?'; lim=1; u=1;
a[1]=1; a[2*n-1]=1; rez=2;
for (i=2; i<2*n-1; ++i) {
if (i>lim){
int lim=i+1; u=i;
while (s[2*i-lim]==s[lim]) ++lim;
--lim;
a[i]=2*(lim-i)+1;
}
else {
int brat=min(lim-i,a[2*u-i]/2+1);
a[i]=2*brat+1;
if (i+brat==lim) {
lim=i+brat+1;
while (s[lim]==s[2*i-lim]) ++lim;
--lim;
a[i]+=2*(lim-i)+1;
}
}
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);
}