Cod sursa(job #1300874)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 25 decembrie 2014 01:10:02
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int NMAX = 1000000;

int n;
char c[2 * NMAX + 10],sir[NMAX + 10];
int p[2 * NMAX + 10];

int main()
{
    long long sol = 0;
    in>>sir;
    n = strlen(sir);
    int m = 0;
    c[0] = '!';
    for(int i = 0 ; i < n ; i++){
        c[++m] = '#';
        c[++m] = sir[i];
    }
    c[++m] = '#';
    c[++m] = '$';
    int C = 0,R = 0;
    for(int i = 1 ; i < m ; i++){
        int o = 2*C-i;
        if(R > i)
            p[i] = min(R-i,p[o]);
        else
            p[i] = 0;
        while(c[(i-p[i]-1)] == c[(i+p[i] + 1)])
            ++p[i];
        if(i + p[i] >= R){
            C = i;
            R = i+p[i];
        }
        if(c[i] == '#')
            sol += p[i]/2;
        else
            sol += p[i]/2 + 1;
    }
    out<<sol;
    return 0;
}