Cod sursa(job #2967470)

Utilizator average_disappointmentManolache Sebastian average_disappointment Data 19 ianuarie 2023 17:48:49
Problema PScPld Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <fstream>
#include <string>

using namespace std;

ifstream cin("pscpld.in");
ofstream cout("pscpld.out");

const int nmax = 1e6;

long long Manacher(string str) {

    int n = str.length();
    if (n == 0)
        return -1;

    n = 2 * n + 1;

    int L[nmax + 1];
    L[0] = 0, L[1] = 1;

    int center = 1, center_right = 2, curr_right = 2;
    int curr_left, len, diff;

    bool expand;

    for (curr_right = 2; curr_right < n; curr_right++) {

        curr_left = 2 * center - curr_right;

        diff = center_right - curr_right;

        expand = 0;

        if (diff >= 0) {

            //case 1
            if (L[curr_left] < diff) {

                L[curr_right] = L[curr_left];
            }
            //case 2
            else if (L[curr_left] == diff && curr_right == n - 1) {

                L[curr_right] = L[curr_left];
            }
            //case 3
            else if (L[curr_left] == diff && curr_right < n - 1) {

                L[curr_right] = L[curr_left];
                expand = 1;
            }
            //case 4
            else if (L[curr_left] > diff) {

                L[curr_right] = diff;
                expand = 1;
            }
        }
        else {

            L[curr_right] = 0;
            expand = 1;
        }

        if (expand) {

            while (((curr_right + L[curr_right]) < n && (curr_right - L[curr_right] > 0))
                   && (((curr_right + L[curr_right] + 1) % 2 == 0)
                   || (str[(curr_right + L[curr_right] + 1) / 2] == str[(curr_right - L[curr_right] - 1) / 2]))) {

                L[curr_right]++;
            }
        }

        if (curr_right + L[curr_right] > center_right) {

            center = curr_right;
            center_right= curr_right + L[curr_right];
        }
    }

    long long ans = (n - 1) / 2;
    for (int i = 0; i < n; i++) {

        if (L[i] > 1) {

            ans += L[i] / 2;
        }
    }

    return ans;
}

int main() {

    string str;
    cin >> str;

    cout << Manacher(str);
}