Cod sursa(job #2886960)

Utilizator hurjui12AlexandruHurjui Alexandru-Mihai hurjui12Alexandru Data 8 aprilie 2022 17:18:09
Problema PScPld Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 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, l, st, dr;
    fin >> buff;
    a += '#';
    for (i = 0; i<buff.size(); i++)
    {
        a += buff[i];
        a += '#';
    }
    n = a.size();
    st = dr = -1;

    for (i = 0; i<n; i++)
    {
        if (i <= dr)
            l = min (dr-i+1, pal[st+dr-i]);
        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)
        {
            st = i-l+1;
            dr = i+l-1;
        }
    }
    long long rasp = 0;
    for (i = 0; i<n; i++)
        rasp = rasp + pal[i]/2;
    fout << rasp;
    return 0;
}