Cod sursa(job #1335970)

Utilizator wGEORGEWGeorge Cioti wGEORGEW Data 6 februarie 2015 10:39:11
Problema PScPld Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#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;
}
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;