Cod sursa(job #2737055)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 4 aprilie 2021 13:03:02
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

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

int len;
int64_t lps[2000100];
string x;

int64_t manacher()
{
    int c = 0, r = 0;

    for(int i = 1; i < len - 1; i++)
    {
        int mirror = 2 * c - i;

        if(i < r)
            lps[i] = min(lps[mirror], (int64_t)r - i);

        int64_t a = i + lps[i] + 1;
        int64_t b = i - lps[i] - 1;

        while(a < len && b >= 0 && x[a] == x[b])
        {
            lps[i]++;
            a++;
            b--;
        }

        if(i + lps[i] > r)
        {
            r = i + lps[i];
            c = i;
        }
    }

    int64_t ans = 0;

    for(int i = 1; i < len - 1; i++)
    {
        //cout << i << ' ' << x[i] << ' ' << lps[i] << '\n';

        if(x[i] == '#')
            ans += lps[i] / 2;
        else
            ans += lps[i] / 2 + 1;
    }

    return ans;
}

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

    int k = aux.size();

    x[len++] = '#';

    for(int i = 0; i < k; i++)
    {
        x[len++] = aux[i];
        x[len++] = '#';
    }

    out << manacher() << '\n';

    return 0;
}