Cod sursa(job #3349963)

Utilizator chatGPTcioc irina chatGPT Data 3 aprilie 2026 21:19:50
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

char s[1000005],t[2000010];
int r[2000010];
int main()
{
    fin>>s;
    int ns=strlen(s);
    int n=0;
    t[n++]='@';
    for(int i=0;i<ns;i++)
    {
        t[n++]='#';
        t[n++]=s[i];
    }
    t[n++]='#';
    t[n++]='$';

    long long tot=0;
    int c=0,m=0; // c=centru, m=margine dreapta

    // 2. Algoritmul Manacher
    for(int i=1;i<n-1;i++)
    {
        int ogl=2*c-i; // oglinda lui i fata de c
        if(i<m)
            r[i]=min(m-i,r[ogl]);
        // Extindere fara spatii la operatori
        while(t[i+(1+r[i])]==t[i-(1+r[i])])
            r[i]++;
        // Update centru si margine
        if(i+r[i]>m)
        {
            c=i;
            m=i+r[i];
        }
        // Adaugam numarul de palindromuri gasite
        tot+=(r[i]+1)/2;
    }
    fout<<tot;
    return 0;
}