Cod sursa(job #2408033)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 17 aprilie 2019 15:18:22
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include<bits/stdc++.h>
using namespace std;

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);

    scanf("%s",s);

    int n=strlen(s);

    int l=0,r=-1;

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

        while((i+k)<n && (i-k)>=0 && 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(even[l+r-i+1],r-i+1)+1;

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

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

    long long sol=0LL;

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

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

    return 0;
}