Cod sursa(job #2699184)

Utilizator dimi999Dimitriu Andrei dimi999 Data 23 ianuarie 2021 19:34:07
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <string>

using namespace std;

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

int Pal[2000005], v[2000005];

void Manacher(string s)
{
    v[0] = -2;
    v[2 * s.size() + 2] = -3;

    for(int i = 1; i <= 2 * s.size() + 1; i += 2)
        v[i] = -1;

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

    int C, R;

    C = R = 0;

    for(int i = 1; i <= 2 * s.size() + 1; i++)
    {
        int mirror = 2 * C - i;

        if(i < R)
            Pal[i] = min(R - i, Pal[mirror]);

        while(v[i + Pal[i] + 1] == v[i - Pal[i] - 1])
            Pal[i]++;

        if(i + Pal[i] > R)
        {
            C = i;
            R = i + Pal[i];
        }
    }

    long long ans = 0;

    for(int i = 1; i <= 2 * s.size() + 1; i++)
        ans += (long long)(Pal[i]  / 2);

    fout << ans + (long long)s.size() << '\n';
}

int main()
{
    string s;

    fin >> s;

    Manacher(s);
    return 0;
}