Pagini recente » Cod sursa (job #1979036) | Cod sursa (job #1235330) | Cod sursa (job #796792) | Cod sursa (job #305065) | Cod sursa (job #1345618)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int nmax= 1000000;
int n, d[2*nmax+5];
string s, a;
int main( ) {
fin>>a;
s.push_back(' '), s.push_back('$'); n= 1;
for ( int i= 0; i<(int)a.size(); ++i ) {
s.push_back(a[i]);
s.push_back('$'); n+= 2;
}
for ( int i= 1, right= 0, pos= 0; i<=n; ++i ) {
if ( i>right ) {
int j;
d[i]= 1;
for ( j= 1; s[i-j]==s[i+j]; ++j ) ; --j;
d[i]+= j, pos= i, right= i+j;
} else {
if ( i+d[2*pos-i]-1<right ) {
d[i]= d[2*pos-i];
} else {
int j;
d[i]= right-i+1;
for ( j= 1; s[2*i-right-j]==s[right+j]; ++j ) ; --j;
d[i]+= j, pos= i, right= right+j;
}
}
}
int sol= 0;
for ( int i= 1; i<=n; ++i ) {
sol= sol+d[i]/2;
}
fout<<sol<<"\n";
return 0;
}