Cod sursa(job #2785839)

Utilizator Diana_IonitaIonita Diana Diana_Ionita Data 19 octombrie 2021 17:44:21
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string s;
void pal()
{
    int n=s.size();
    if(n==0)
        return;
    n=2*n+1;
    int l[n];
    l[0]=0;
    l[1]=1;
    int c=1;
    int r=2;
    int i=0;
    int imirror;
    int maxl=1;
    int maxc=0;
    int start=-1;
    int end=-1;
    int diff=-1;
    for(i=2; i<n; i++)
    {
        imirror=2*c-i;
        l[i]=0;
        diff=r-i;
        if(diff>0)
            l[i]=min(l[imirror],diff);
        while(((i+l[i])<n&&(i-l[i])>0)&&
                (((i+l[i]+1)%2==0)||
                 (s[(i+l[i]+1)/2]==s[(i-l[i]-1)/2])))
        {
            l[i]++;
        }

        if(l[i]>maxl)
        {
            maxl=l[i];
            maxc=i;
        }
        if(i+l[i]>r)
        {
            c=i;
            r=i+l[i];
        }
    }
    long long sum=0;
    for(i=0; i<n; i++)
    {//fout<<(l[i]+1)/2<<'\n';
        sum+=(l[i]+1)/2;
    }
    fout<<sum;
}

int main()
{
    fin>>s;
    pal();
    return 0;
}