Pagini recente » Cod sursa (job #2105609) | Cod sursa (job #835229) | Cod sursa (job #2038301) | Cod sursa (job #717146) | Cod sursa (job #1320742)
#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= 0;
for ( int i= 0; i<n; ++i ) {
int aux= 0;
if ( c+p[c]>=i ) {
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= n/2;
for ( int i= 0; i<n; ++i ) {
sol+= p[i]/2;
}
fout<<sol<<"\n";
return 0;
}