Cod sursa(job #2307192)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 23 decembrie 2018 22:32:11
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <string>

using namespace std;

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

int drMax, posDrMax, manacher[2000005];
long long sol;
string s, a;

int main()
{
    fin >> s;

    a += '*';
    for(int i = 0; i < s.size(); i++)
        a += s[i], a += '*';

    drMax = posDrMax = manacher[0] = 0;
    for(int i = 1; i < a.size(); i++)
    {
        if(i > drMax)
        {
            int st = i - 1;
            int dr = i + 1;
            while(a[st] == a[dr] && st >= 0 && dr < a.size())
                st--, dr++;
            st++, dr--;

            manacher[i] = dr - i;

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

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

            manacher[i] = dr - i;

            drMax = dr;
            posDrMax = i;
        }

        if(a[i] == '*')
            sol += (manacher[i] + 1) / 2;
        else
            sol += (manacher[i] + 2) / 2;
    }

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