Cod sursa(job #2317008)

Utilizator mirunazMiruna Zavelca mirunaz Data 12 ianuarie 2019 17:46:56
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
using namespace std;

int main() {
    ifstream in("pscpld.in");
    ofstream out("pscpld.out");

    string s;
    in >> s;
    int m = s.size();
    int v[2 * m];
    char a[2 * m];

    for (int i = 0; i < m; i++) {
        a[2 * i] = s[i];
        a[2 * i + 1] = '*';
    }
    m = 2 * m - 1;
    a[m] = '\0';

    //Manacher
    int j, centru = 0, dr = 0, sol = 0;
    for (int i = 0; i < m; i++) {
        if (dr <= i) {
            v[i] = 1;
            j = 1;

            while (i - j >= 0 && i + j < m && a[i - j] == a[i + j]) {
                j++;
                v[i]++;
            }

            dr = i + j - 1;
            centru = i;
        } else {
            v[i] = min(dr - i + 1, v[2 * centru - i]);

            if (v[i] + i - 1 >= dr) {
                j = v[i];
                while (i - j >= 0 && i + j < m && a[i - j] == a[i + j]) {
                    j++;
                    v[i]++;
                }

                dr = i + j - 1;
                centru = i;
            }
        }

        if (a[i] != '*') {
            sol += (v[i] + 1) / 2;
        } else {
            sol += v[i] / 2;
        }
    }

    out <<sol;
    return 0;
}