Cod sursa(job #2774396)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 11 septembrie 2021 15:34:42
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const ll NMAX = 2000005;
char c[NMAX],a[NMAX];
ll n,P[NMAX],rasp=0;
ll minim(ll x,ll y){
    if(x<y) return x;
    return y;
}
void citire(){
    fin >> (c+1);
    n=strlen(c+1);
    for(ll i=1;i<=n;i++){
        a[i*2-1]='#';
        a[i*2]=c[i];
    }
    a[n*2+1]='#';
    n=2*n+1;
}
void pscpld(){
    ll c=0,dr=0;
    for(ll i=1;i<n;i++){
        if(i<=dr) P[i]=minim(P[2*c-i],dr-i);
        while(i+P[i]+1<n and i-P[i]-1>=0 and a[i+P[i]+1]==a[i-P[i]-1]) P[i]++;
        if(i+P[i]>dr){
            dr=i+P[i];
            c=i;
        }
    }
}
void solve(){
    for(ll i=1;i<=n;i++){
        if(i%2==1) rasp+=(P[i]+1)/2;
        else       rasp+=P[i]/2+1;
    }
}
void afis(){
    fout << rasp;
}
int main()
{
    citire();
    pscpld();
    solve();
    afis();
    return 0;
}