Cod sursa(job #3284752)

Utilizator Tudor_CCTudor Cocu Tudor_CC Data 12 martie 2025 09:57:06
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <bits/stdc++.h>

using namespace std;

string s,t;

long long int p[2000006];

int main()
{
    ifstream cin("pscpld.in");
    ofstream cout("pscpld.out");
    cin>>s;
    for(int i=0;i<s.size();++i)
    {
        t+="#";
        t+=s[i];
    }
    t+="#";
    long long int cnt=0,c=0,r=0;
    for(int i=0;i<t.size();++i)
    {
        int mir=2*c-i;
        if(i<r)
        {
            p[i]=min(r-i,p[mir]);
        }
        while(i+p[i]+1<t.size() && i-p[i]-1>=0 && t[i+p[i]+1]==t[i-p[i]-1])
        {
            p[i]++;
        }
        if(i+p[i]>r)
        {
            c=i;
            r=i+p[i];
        }
        cnt=cnt+(p[i]+1)/2;
    }
    cout<<cnt;
    return 0;
}