Cod sursa(job #3156168)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 10 octombrie 2023 18:44:40
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <string>

using namespace std;

const long long max_size = 1e6 + 3;

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

int p[2 * max_size];

signed main ()
{
    string x, s;
    in >> x;
    s += '$';
    for (long long i = 0; i < x.size(); i++)
    {
        s += x[i];
        s += '$';
    }
    long long ans = 0;
    int dr = 0, n = s.size() - 1, poz = 0;
    for (int i = 1; i <= n; i++)
    {
        long long x = 2 * poz - 1;
        if (dr > i)
        {
            p[i] = min(p[x], dr - i);
        }
        while (i >= p[i] + 1 && i + p[i] - 1 <= n && s[i - p[i] - 1] == s[i + p[i] + 1])
        {
            p[i]++;
        }
        if (i + p[i] > dr)
        {
            dr = i + p[i];
            poz = i;
        }
        if (i % 2 == 1)
        {
            ans += 1LL * (p[i] + 1) / 2;
        }
        else
        {
            ans += 1LL * p[i] / 2;
        }
    }
    out << ans;
    in.close();
    out.close();
    return 0;
}