Cod sursa(job #3209746)

Utilizator SSKMFSS KMF SSKMF Data 3 martie 2024 14:04:33
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <cstring>
using namespace std;

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

int lungime_palindrom[2000002];
char sir[2000002];

int main ()
{
    cin >> sir;

    int lungime = strlen(sir);
    for (int indice_1 = lungime - 1 , indice_2 = ((lungime <<= 1)++) ; indice_1 >= 0 ; indice_1-- , indice_2 -= 2)
        { sir[indice_2] = '|'; sir[indice_2 - 1] = sir[indice_1]; }

    sir[0] = '|';
    for (int centru = 0 , lungime_actuala = 0 ; centru < lungime ; )
    {
        while (lungime_actuala <= centru && centru + lungime_actuala < lungime && sir[centru - lungime_actuala] == sir[centru + lungime_actuala])
            { lungime_actuala++; }
        
        lungime_palindrom[centru] = lungime_actuala; lungime_actuala = 0;
        for (int initial = centru++ , stanga = initial - 1 ; centru < initial + lungime_palindrom[initial] ; stanga-- , centru++) {
            if (stanga - lungime_palindrom[stanga] > initial - lungime_palindrom[initial])
                { lungime_palindrom[centru] = lungime_palindrom[stanga]; }
            else
                if (stanga - lungime_palindrom[stanga] < initial - lungime_palindrom[initial])
                    { lungime_palindrom[centru] = initial + lungime_palindrom[initial] - centru; }
                else
                    { lungime_actuala = lungime_palindrom[stanga]; break; }
        }
    }

    uint64_t total = 0;
    for (int indice = 0 ; indice < lungime ; indice++)
        { total += (lungime_palindrom[indice] >> 1); }

    cout << total;
    cout.close(); cin.close();
    return 0;
}