Pagini recente » Cod sursa (job #1046413) | Cod sursa (job #1343472) | Cod sursa (job #714140) | Cod sursa (job #1310171) | Cod sursa (job #1019155)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
typedef long long i64;
const int nmax= 1000000;
string s;
int po[nmax+1], pe[nmax+1];
int main( ) {
fin>>s;
int n= s.size();
i64 sol= 0;
int cp= -1;
for ( int i= 0; i<n; ++i ) {
int aux;
if ( cp==-1|| cp+po[cp]<i ) {
aux= 0;
} else {
aux= min(po[2*cp-i], cp+po[cp]-i);
}
while ( i-aux-1>=0&& i+aux+1<n&& s[i-aux-1]==s[i+aux+1] ) {
++aux;
}
po[i]= aux;
if ( cp+po[cp]<i+po[i] ) {
cp= i;
}
sol+= po[i]+1;
}
cp= 0;
for ( int i= 1; i<n; ++i ) {
if ( s[i-1]==s[i] ) {
int aux;
if ( cp+pe[cp]-1<i ) {
aux= 1;
} else {
aux= min(pe[2*cp-i], cp+pe[cp]-1-i);
}
while ( i-aux-1>=0&& i+aux<n&& s[i-aux-1]==s[i+aux] ) {
++aux;
}
pe[i]= aux;
if ( cp+pe[cp]-1<i+pe[i]-1 ) {
cp= i;
}
sol+= pe[i];
}
}
fout<<sol<<"\n";
return 0;
}