Cod sursa(job #3150684)

Utilizator Alex_BerbescuBerbescu Alexandru Alex_Berbescu Data 17 septembrie 2023 22:58:37
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#include <bits/stdc++.h>
using namespace std;
string s, t;
char c;
int pal[2000005], n, st, dr, start, maxi, le, ri;
long long sol;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int32_t main(int argc, char * argv[])
{
    fin >> t;
    for(int i = 0; t[i]; ++i)
    {
        s.push_back('#');
        s.push_back(t[i]);
    }
    s.push_back('#');
    n = s.length() - 1;
    for(int i = 0; i <= n; ++i)
    {
        if(i < dr)
        {
            pal[i] = min(dr - i, pal[st + dr - i]);
        }
        while(i - pal[i] >= 0 && i + pal[i] <= n && s[i - pal[i]] == s[i + pal[i]])
        {
            pal[i]++;
        }
        if(i + pal[i] - 1 > dr)
        {
            dr = i + pal[i] - 1;
            st = i - pal[i] + 1;
        }
        if(maxi < pal[i])
        {
            maxi = pal[i];
            start = (i - pal[i] + 1) / 2;  // maxi - 1 lungimea celui mai lung si end va fi start + maxi - 2

        }
    }
    for(int i = 0; i <= n; ++i)
    {
        sol += pal[i] / 2;
    }
    fout << sol;
    return 0;

}