Pagini recente » Cod sursa (job #2066712) | Cod sursa (job #2227136) | Cod sursa (job #131892) | Cod sursa (job #240187) | Cod sursa (job #1335949)
#include<fstream>
#include<string>
using namespace std;
ifstream fin( "pscpld.in" );
ofstream fout( "pscpld.out" );
const int nmax = 2000001;
long long d[ nmax + 1 ];
string s, aux;
inline int min2( int x, int y ) {
if ( x < y ) {
return x;
}
return y;
}
int main() {
int j;
fin >> aux;
for( string::iterator it = aux.begin(); it != aux.end(); ++ it ) {
s += "$";
s += *it;
}
s += "$";
aux.clear();
j = 0;
for( int i = 0; i < ( int )s.size(); ++ i ) {
if ( i <= j + d[ j ] ) {
d[ i ] = min2( d[2 * j - i], d[ j ] + j - i );
}
while ( i - d[ i ] >= 0 && i + d[ i ] < ( int )s.size() && s[ i - d[ i ] ] == s[ i + d[ i ] ] ) {
++ d[ i ];
}
if ( i + d[ i ] > j + d[ j ] ) {
j = i;
}
}
long long ans = 0;
for( int i = 0; i < ( int )s.size(); ++ i ) {
ans += d[ i ] / 2;
}
fout << ans << "\n";
fin.close();
fout.close();
return 0;
}