Cod sursa(job #2941727)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 18 noiembrie 2022 09:54:54
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <string>

const int NMAX = 2e6 + 5;
using namespace std;

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

int N;
long long ans;
int manacher[NMAX];
string tmp, s;

inline string get_manacher_string(string tmp)
{
    string s = "$";
    for (auto c: tmp)
    {
        s += "#";
        s += c;
    }
    s += "#^";

    return s;
}

inline void get_manacher()
{
    N = s.length();
    int mid = 0, dr = 0, mirr;

    for (int i = 1 ; i < N - 1 ; ++ i)
    {
        mirr = mid + mid - i;

        if (i <= dr)
        {
            manacher[i] = min(manacher[mirr], dr - i);
        }

        while (s[i - manacher[i] - 1] == s[i + manacher[i] + 1])
            manacher[i] ++;
        
        if (i + manacher[i] > dr)
        {
            dr = i + manacher[i];
            mid = i;
        }
    }
}

int main()
{
    f >> tmp;
    s = get_manacher_string(tmp);
    get_manacher();

    for (int i = 1 ; i < N - 1 ; ++ i)
    {
        ans += 1LL * (manacher[i] + 1) / 2;
    }

    g << ans;
}