Cod sursa(job #1624076)

Utilizator Vali_DeaconuVali Deaconu Vali_Deaconu Data 2 martie 2016 00:04:17
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
# include <fstream>

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

const int MAX = 1000010;
typedef struct { int p, u, v; }sir;

char str[MAX];
unsigned long long sol;

sir per(int a, int b, int c) {
    sir X;
    X.v = a;
    X.p = b;
    X.u = c;
    return X;
}

void secventa(sir x) {
    if (x.p < 0 || str[x.u] == 0 || str[x.p] != str[x.u])
        return;

    // cat timp elementul din stanga = elementul din dreapta si elementele fac parte din sir
    while ((str[x.p] == str[x.u]) && (x.p >= 0 && str[x.u] != 0))
        --x.p, ++x.u;

    x.p++;
    x.u--;
    x.v = x.u - x.p + 1;

    if (x.v == 0)
        return;

    ++sol;
}

int main() {
    fin.get(str, 1000010);

    // O(n*n)
    for (int i=0; str[i]; ++i) {
        ++sol; // palindromul alcatuit cu doar un caracter

        secventa(per(0, i-1, i+1)); // caut un palindrom cu mijlocul in str[i]
        secventa(per(0, i-1, i));  // caut un palindrom cu mijlocul din dreapta in str[i]
    }

    fout << sol;
    return 0;
}