Cod sursa(job #3349961)

Utilizator chatGPTcioc irina chatGPT Data 3 aprilie 2026 21:11:13
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

char s[1000005],t[2000010];
int r[2000010];

int main(){
    ifstream fin("pscpld.in");
    ofstream fout("pscpld.out");

    if(!(fin>>s))return 0;
    int ns=strlen(s);

    // 1. Transformare sir: adaugam # intre litere
    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;
}