Cod sursa(job #2806242)

Utilizator namesurname01Name Surname namesurname01 Data 22 noiembrie 2021 14:31:52
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#define N 1000004
#include <cstring>

using namespace std;

char ch[2 * N], s[N];
int lp[2 * N];

int main()
{
    ifstream f("pscpld.in");
    ofstream g("pscpld.out");
    int n, c, lg, exp, dr, i, ii;
    f >> ch;
    n = strlen(ch);
    lg = -1;
    for (i = 0;i < n;++i)
    {
        s[++lg] = '!';
        s[++lg] = ch[i];
    }
    s[++lg] = '!';
    long long ss = n;
    c = 1, dr = 2;
    lp[1] = 1;
    for (i = 2;i <= lg;++i)
    {
        ii = c - (i - c);
        exp = 0;
        if (dr <= i)
            exp = 1;
        else
        {
            if (lp[ii] < dr - i)///se gaseste in palindromul mare, dar nu e prefix
                lp[i] = lp[ii];
            else
                if (lp[ii] == dr - i)///e prefix al palindromului mare
                    lp[i] = lp[ii], exp = 1;
                else
                    if (lp[ii] > dr - i)///se afla in exteriorul palindromului
                        lp[i] = dr - i, exp = 1;
        }
        if (exp)
        {
            while (i - lp[i] - 1 >= 0 && i + lp[i] + 1 <= lg)
                if ((i - lp[i]) % 2 != 0)
                    ++lp[i];
                else
                    if (s[i - lp[i] - 1] == s[i + lp[i] + 1])
                        ++lp[i];
                    else
                        break;
        }
        if (dr < i + lp[i])
            dr = i + lp[i], c = i;
        ss = ss + (long long)lp[i] / 2;
    }
    g << ss << '\n';
    f.close();
    g.close();
    return 0;
}