Cod sursa(job #2650379)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 18 septembrie 2020 16:33:54
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1000007;

string rd;

vector<int> pal_array(string s)
{
    int n = s.size();
    s = "@" + s + "$";
    vector<int> len(n + 1);
    int l = 1, r = 1;
    for(int i = 1; i <= n; i++)
    {
        len[i] = min(r - i, len[l + (r - i)]);
        while(s[i - len[i]] == s[i + len[i]])
            len[i]++;
        if(i + len[i] > r)
        {
            l = i - len[i];
            r = i + len[i];
        }
    }
    len.erase(begin(len));
    return len;
}

int main()
{
    in >> rd;
    string s = "";
    s.resize(2*rd.size() + 1);

    for(int index = 0; index < rd.size(); index++)
    {
        s[2*index] = '|';
        s[2*index + 1] = rd[index];
    }
    s[2*rd.size()] = '|';

    //out << s << endl;

    auto p = pal_array(s);

    long long sum = 0;
    for(int i = 0; i < p.size(); i++)
    {
        //out << p[i] << " ";

        if(i%2 == 1)
        {
            sum += (p[i]+1)/2;
        }
        else
        {
            sum += (p[i])/2;
        }
    }

    out << sum;
}