Cod sursa(job #932367)

Utilizator vendettaSalajan Razvan vendetta Data 28 martie 2013 21:04:10
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("pscpld.in");
ofstream g("pscpld.out");

#define nmax 1000005
#define ll long long

string A, S;
int z[nmax*2];

void citeste(){
    getline(f, A);
    for(int i=0; i<A.size()-1; ++i){
        S += A[i]; S += '*';
    }
    S += A[A.size()-1];
}

inline int extinde(int st, int dr){
    int cnt = 0;
    for(int i=st, j=dr; i>=0 && j<S.size(); --i, ++j){
        if (S[i] != S[j]) return cnt;
        ++cnt;
    }
    return cnt;
}

void bagaZvalues(){
    z[0] = 0; int centru = -1; int dr = -1;
    for(int i=1; i<S.size(); ++i){
        if (dr < i){
            z[i] = extinde(i-1, i+1);
            if (z[i] != 0){
                centru = i; dr = i + z[i];
            }
            continue;
        }else{
            int i2 = centru - (i-centru);// simetricul lui i in raport cu centru
            int lungBeta = dr - i; // fac abstractie de punctul i
            if (z[i2] < lungBeta){
                z[i] = z[i2]; continue;
            }
            z[i] = lungBeta + extinde(i - lungBeta -1 , i + lungBeta + 1);
            if (i + z[i] > dr){
                centru = i; dr = i + z[i];
            }
        }
    }
}

void rezolva(){
    // z[i] = cat de mult ma pot duce in stanga si in dreapta evident
    bagaZvalues();
    // le numar
    int cnt = 0;
    for(int i=0; i<S.size(); ++i){
        if (S[i] == '*'){
            cnt += z[i] / 2 + (z[i] % 2);
        }else {
            cnt += z[i] / 2 + 1;// +1 pt ca il iau doar pe el (pe i);
        }
    }
    g << cnt << "\n";
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}