Cod sursa(job #3024917)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 17 martie 2023 11:04:57
Problema PScPld Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb

#include <fstream>

using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
char a[1000010];
char x;
int k;
int rz[1000010];
int main()
{
    a[k++]='#';
    while(cin>>x)
    {
        a[k++]=x;
        a[k++]='#';
    }
    int r=0,l=0;
    for(int i=0;i<k;i++)
    {
        if(i>r)
          rz[i]=0;
        else
          rz[i]=min(r-i,rz[l+r-i]);
        while(i-rz[i]>=0 && a[i-rz[i]]==a[i+rz[i]])
          rz[i]++;
        rz[i]--;
        if(i+rz[i]>r)
        {
            r=i+rz[i];
            l=i-rz[i];
        }
    }
    long long suma=0;
    for(int i=0;i<k;i++)
        suma=suma+(rz[i]+1)/2;
        cout<<suma;
    return 0;
}