Cod sursa(job #2575405)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 6 martie 2020 13:19:24
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<bits/stdc++.h>
using namespace std;

int l,r;

const int maxN=(1e6)+5;
char s[maxN];

int k,odd[maxN],even[maxN];

int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);

    l=0;
    r=-1;

    scanf("%s",s);

    int n=strlen(s);

    for(int i=0;i<n;i++)
    {
        if(i>r) k=1;
            else k=min(r-i,odd[l+r-i]);

        while((i-k)>=0 && (i+k)<n && s[i+k]==s[i-k]) k++;

        odd[i]=k;

        k--;

        if(i+k>r)
        {
            r=i+k;
            l=i-k;
        }
    }

    l=0;
    r=-1;

    for(int i=0;i<n;i++)
    {
        if(i>r) k=1;
            else k=min(r-i+1,even[l+r-i+1])+1;

        while((i-k)>=0 && (i+k-1)<n && s[i-k]==s[i+k-1]) k++;

        k--;

        even[i]=k;

        if((i+k-1)>r)
        {
            r=i+k-1;
            l=i-k;
        }
    }


    long long sol=0;

    for(int i=0;i<n;i++)
        sol=sol+1LL*(odd[i]+even[i]);

    printf("%lld\n",sol);

    return 0;
}