Cod sursa(job #3272665)

Utilizator tudor_costinCostin Tudor tudor_costin Data 30 ianuarie 2025 18:11:20
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>

using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int Nmax=1e6+5;
int p[Nmax];
signed main()
{
    string s;
    fin>>s;
    vector<char> t;
    for(auto ch:s)
    {
       t.push_back('#');
       t.push_back(ch);
    }
    t.push_back('#');
    int n=t.size()-2;
    int sol=0;
    int l=1,r=1;
    for(int i=1;i<=n;i++)
    {
        p[i]=max(0,min(r-i,p[l+(r-i)]));
        while(i-p[i]>=0 && i+p[i]<=n+1 && t[i-p[i]]==t[i+p[i]])
        {
            p[i]++;
        }
        sol+=(p[i])/2;
        if(i+p[i]>r)
        {
            r=i+p[i],l=i-p[i];
        }
    }
    fout<<sol<<'\n';
    return 0;
}