Cod sursa(job #2884228)

Utilizator hurjui12AlexandruHurjui Alexandru-Mihai hurjui12Alexandru Data 2 aprilie 2022 17:25:28
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <string>
using namespace std;

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

string a, buff;
int pal[2000001];

int main()
{
    int n, i, st, dr, l;

    fin >> buff;
    a.push_back ('#');
    for (i = 0; i<buff.size(); i++)
    {
        a.push_back (buff[i]);
        a.push_back ('#');
    }

    n = a.size();
    st = dr = -1;
    for (i = 0; i<n; i++)
    {
        if (i <= dr)
            l = min (pal[st+dr-i], dr-i+1);
        else
            l = 1;

        while (0 <= i-l && i+l<n && a[i-l] == a[i+l])
            l++;

        pal[i] = l;
        if (i+l-1 > dr)
        {
            dr = i+l-1;
            st = i-l+1;
        }
    }

    long long rasp = 0;
    for (i = 0; i<n; i++)
        rasp = rasp + pal[i]/2;
    fout << rasp;
    return 0;
}