Pagini recente » Cod sursa (job #2753236) | Cod sursa (job #1810859) | Cod sursa (job #1798147) | Cod sursa (job #1473644) | Cod sursa (job #1019164)
#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, v;
int p[nmax*2+1];
int main( ) {
fin>>s;
int n= s.size();
for ( int i= 0; i<n; ++i ) {
v+='$'; v+=s[i];
}
v+='$';
n= v.size();
int c= -1;
for ( int i= 0; i<n; ++i ) {
int aux;
if ( c==-1|| c+p[c]<i ) {
aux= 0;
} else {
aux= min(p[2*c-i], c+p[c]-i);
}
while ( i-aux-1>=0&& i+aux+1<n&& v[i-aux-1]==v[i+aux+1] ) {
++aux;
}
p[i]= aux;
if ( c+p[c]<i+p[i] ) {
c= i;
}
}
i64 sol= 0;
for ( int i= 1; i<n; i+= 2 ) {
sol+= p[i];
}
fout<<sol<<"\n";
return 0;
}