Cod sursa(job #2416635)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 27 aprilie 2019 20:19:09
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>
#include <string>

using namespace std;

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

const int NMAX = 1000000;

long long ans;
int manacher[2 * NMAX + 5];
string s;

void Manacher()
{
    int drMax = 0;
    int posDrMax = 0;

    for(int i = 1; i < s.size(); i++)
    {
        if(i > drMax)
        {
            int st = i - 1;
            int dr = i + 1;

            while(s[st] == s[dr] && st >= 0 && dr < s.size())
                st--, dr++;

            st++, dr--;
            manacher[i] = dr - i;

            drMax = dr;
            posDrMax = i;
        }
        else
        {
            if(i + manacher[2 * posDrMax - i] < drMax)
                manacher[i] = manacher[2 * posDrMax - i];
            else
            {
                int st = 2 * i - drMax;
                int dr = drMax;

                while(s[st] == s[dr] && st >= 0 && dr < s.size())
                    st--, dr++;

                st++, dr--;
                manacher[i] = dr - i;

                drMax = dr;
                posDrMax = i;
            }
        }

        if(s[i] == '$')
            ans += 1LL * (manacher[i] + 1) / 2;
        else
            ans += 1LL * (manacher[i] + 2) / 2;
    }
}

int main()
{
    string aux;
    fin >> aux;

    s += '$';
    for(auto it : aux)
        s += it, s += '$';

    Manacher();

    fout << ans << '\n';
    return 0;
}