Cod sursa(job #3247201)

Utilizator Sasha_12454Eric Paturan Sasha_12454 Data 6 octombrie 2024 12:25:38
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <bits/stdc++.h>

const std :: string FILENAME = "pscpld";

std :: ifstream f (FILENAME + ".in");

std :: ofstream g (FILENAME + ".out");

const long long NMAX = 2e6 + 5;

long long ans;

long long p[NMAX];

std :: string s;

inline std :: string modif(const std :: string & s)
{
    std :: string aux = "@";

    for(auto & i : s)
    {
        aux += "#";

        aux += i;
    }

    aux += "#*";

    return aux;
}

inline void manacher(const std :: string & s)
{
    long long r = 0;

    long long c = 0;

    for(long long i = 1; i < s.size() - 1; i ++)
    {
        long long sim = 2 * c - i;

        if(i < r)
        {
            p[i] = std :: min(r - i, p[sim]);
        }

        while(s[i - p[i] - 1] == s[i + p[i] + 1])
        {
            p[i] ++;
        }

        if(r < i + p[i])
        {
            r = p[i];

            c = i;
        }
    }
}

int main()
{

    f >> s;

    s = modif(s);

    manacher(s);

    for(long long i = 1; i < s.size() - 1; i ++)
    {
        ans += ceil(1.00 * p[i] / 2);
    }

    g << ans;

    return 0;
}