Cod sursa(job #2840663)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 28 ianuarie 2022 16:27:12
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("pscpld.in");
ofstream g("pscpld.out");

using ll = long long;

const int NMAX = 1e6 + 1;

int N, M;
char A[NMAX], S[(NMAX << 1)];

int Z[(NMAX << 1)];

static inline void Read ()
{
    f.tie(nullptr);

    f >> (A + 1), N = (int)strlen(A + 1);

    for(int i = 1; i < N; ++i)
        S[++M] = A[i], S[++M] = '#';

    S[++M] = A[N];

    return;
}

static inline int my_min (int a, int b)
{
    return ((a < b) ? a : b);
}

static inline void Solve ()
{
    int L = 0, R = 0;

    Z[1] = 1;

    for(int i = 2; i <= M; ++i)
    {
        if(i <= R)
            Z[i] = my_min(R - i + 1, Z[L + R - i]);

        while(i - Z[i] >= 1 && i + Z[i] <= M && S[i - Z[i]] == S[i + Z[i]])
            ++Z[i];

        if(i + Z[i] - 1 > R)
            L = i - Z[i] + 1, R = i + Z[i] - 1;
        else if(i + Z[i] - 1 == R && i - Z[i] + 1 > L)
            L = i - Z[i] + 1;
    }

    return;
}

static inline void Find_Ans ()
{
    ll ans = 2;

    for(int i = 2; i < M; ++i)
        ans += 1LL * ((Z[i] + (bool)(S[i] != '#')) >> 1);

    g << ans << '\n';

    return;
}

int main()
{
    Read();

    Solve();

    Find_Ans();

    return 0;
}