Pagini recente » Cod sursa (job #2446462) | Cod sursa (job #2104385) | Cod sursa (job #2523308) | Cod sursa (job #2242008) | Cod sursa (job #1345620)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
typedef long long i64;
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;
}
}
}
i64 sol= 0;
for ( int i= 1; i<=n; ++i ) {
sol= (i64)sol+d[i]/2;
}
fout<<sol<<"\n";
return 0;
}