Cod sursa(job #3350823)

Utilizator CarenaMironov Cezar Luca Carena Data 13 aprilie 2026 17:08:30
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>

using namespace std;

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

const int NMAX=1e6+5;
int n, ans, p[NMAX];
string s, t;

int sim(int x, int y)
{
    return 2*y-x;
}

int main()
{
    in>>s; n=s.size();
    for(int i=0;i<n;i++)
        t+='$', t+=s[i];
    t+='$';
    n=t.size();
    int k=0;
    for(int i=1;i<n;i++)
    {
        if(i<=k+p[k])
            p[i]=min(p[sim(i, k)], k+p[k]-i);
        if(i+p[i]>=k+p[k])
        {
            while(i+p[i]+1<n && t[i+p[i]+1]==t[sim(i+p[i]+1, i)])
                p[i]++;
            k=i;
        }
        ans+=(p[i]+1)/2;
    }
    out<<ans;
    return 0;
}