Cod sursa(job #2582752)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 17 martie 2020 12:42:20
Problema PScPld Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

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

string x;
int lps[1000010];

int solveUsingManacher()
{
    int sze = x.size();
    int c = 0, r = 0;

    for(int i = 0; i < sze; i++)
    {
        //cout << i;

        int mirror = 2*c - i;

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

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

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

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

            c = i;
        }
    }

    /*for(int i = 0; i < sze; i++)
            cout << x[i] << ' ';

    cout << '\n';

    for(int i = 0; i < sze; i++)
            cout << lps[i] << ' ';*/

    int cont = 0;

    for(int i = 0; i < sze; i++)
    {
        if(x[i] == '#')
            cont += lps[i]/2;
        else
            cont += (lps[i] - 1)/2 + 1;
    }

    return cont;
}

int main()
{
    in >> x;

    int sze = x.size() * 2 + 1;

    for(int i = 0; i < sze; i += 2)
        x.insert(i, "#");

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

    return 0;
}