Pagini recente » Cod sursa (job #2738096) | Cod sursa (job #932518) | Cod sursa (job #223178) | Cod sursa (job #1093817) | Cod sursa (job #578658)
Cod sursa(job #578658)
#include <fstream>
#define Nmax 1000003
#define LL long long
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char s[Nmax];
int lg[2][Nmax];
int N;
inline int Minim(int x,int y){ return x<y ? x:y ; }
int main(){
int i,j,dist,dcc,cc,cc2,st,dr,is,id; LL sol;
fin>>s+1;
for(N=1; s[N]>='a' && s[N]<='z'; ) ++N;
--N;
dr=0; cc=0;
for(i=1;i<=N;++i){
// impar
if( dr>=i ){
dist=dr-i+1;
dcc=i-cc;
st=cc-dcc+(cc2!=0);
}
else st=i, dist=1,lg[0][i]=1;
lg[0][i]=Minim(lg[0][st],dist);
if( lg[0][i] && lg[0][i]%2==0 ) lg[0][i]--;
for( is=i-lg[0][i]/2-1, id=i+lg[0][i]/2+1; is>=1 && id<=N &&s[is]==s[id]; --is,++id )
lg[0][i]+=2;
id--;
if( id>dr ) dr=id, cc=i, cc2=0;
// par
if( s[i]!=s[i+1] ) continue;
if( dr>=i+1 ){
dist=dr-(i+1)+1;
dcc=(i+1)-cc;
st=cc-dcc+(cc2!=0);
}
else st=i, dist=2, lg[1][i]=2;
lg[1][i]=Minim(lg[1][st],dist);
if( lg[1][i]&1 ) lg[1][i]--;
for( is=i-lg[1][i]/2, id=i+1+lg[1][i]/2; is>=1 && id<=N &&s[is]==s[id]; --is,++id )
lg[1][i]+=2;
id--;
if( id>dr ) dr=id, cc=i, cc2=i+1;
}
sol=0;
for(i=1;i<=N;++i)
sol+=1LL*(lg[0][i]+1)/2+1LL*lg[1][i]/2;
fout<<sol<<"\n";
fin.close(); fout.close();
return 0;
}