Cod sursa(job #908613)

Utilizator vendettaSalajan Razvan vendetta Data 9 martie 2013 20:39:31
Problema PScPld Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 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 1000004
#define ll long long

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

void citeste(){
    getline(f, A);
}

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 bagaManacher(){
    //lung[i] = cat de mult ma pot extine de la dreapta(evident si la stanga); e mai ok asa
    lung[0] = 0;
    int st = -1; int dr = -1;
    int centru = -1;
    for(int i=1; i<S.size(); ++i){
        if (dr < i){
            lung[i] = extinde(i-1, i+1);
            st = i - lung[i]; dr = i + lung[i];
            centru = i;
            continue;
        }
        // acum dr >= i(i intra in zBox)
        int i2 = centru - (i-centru);// simentricul lui i fata de centru
        int lungBeta = dr - i;// secventa i+1..dr; fac abstractie de caracatul i;
        if (lung[i2] < lungBeta) lung[i] = lung[i2];// clar
        else {
            lung[i] = lungBeta + extinde(i-lungBeta-1, i+lungBeta+1);
        }
        st = i - lung[i]; dr = i + lung[i];
        centru = i;
    }
}

void rezolva(){
    //algoritmul lui manacher

    for(int i=0; i<A.size()-1; ++i){
        S += A[i]; S+='#';
    }
    S += A[ A.size()-1 ];
    //cout << S << "\n";

    bagaManacher();
    // acum numar secventele palindroame
    ll Rez = 0;
    for(int i=0; i<S.size(); ++i){
        //cout << lung[i] << " ";
        if (S[i] == '#'){// acum e palindrom de genul i, i+1 in vechiul string
            int cnt = lung[i]/2 + (lung[i]%2); // lungimea palindromului va fi 2 * cnt; dar in totla sunt doar cnt palindroame cu centrul in i,i+1
            Rez += (ll)cnt;
        }else {// e simplu de centru i
            int cnt = lung[i]/2 + 1;
            Rez += (ll)cnt;
        }
    }
    //cout << Rez << "\n";
    g << Rez << "\n";
}

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

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

    return 0;
}