Cod sursa(job #2956525)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 19 decembrie 2022 18:37:09
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <string>

using namespace std;

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

const int max_size = 2e6 + 5;

int umbrela[max_size];

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