Cod sursa(job #2317057)

Utilizator mirunazMiruna Zavelca mirunaz Data 12 ianuarie 2019 18:45:56
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 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] = '*';
        a[2 * i + 1] = s[i];
    }
    a[2 * m] = '*';
    a[2 * m + 1] = '\0';
    m = 2 * m + 1;

    //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;
            }
        }

        sol += v[i] / 2;
    }

    out << sol;
    return 0;
}