Cod sursa(job #2068963)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 18 noiembrie 2017 11:41:14
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[1000002];
int lsc[2000006],c,r,n;
int poz(int x)
{
    return 2*x+1;
}
void palind()
{
    c=1;
    r=2;
    n=2*strlen(a)+1;
    bool exp;
    int iMirror;
    for(int i=2; i<n; i++)
    {
        exp=false;
        iMirror=2*c-i;
        lsc[i]=0;
        if(r-i)
        {
            lsc[i]=min(lsc[iMirror],r-i);
        }
            while (((i + lsc[i]) < n && (i - lsc[i]) > 0) &&
                    ( ((i + lsc[i] + 1) % 2 == 0) ||
                      (a[(i + lsc[i] + 1)/2] == a[(i-lsc[i]-1)/2] )))
            {
                lsc[i]++;
            }

        if(i+lsc[i]>r)
        {
            c=i;
            r=i+lsc[i];
        }
    }
}
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    scanf("%s",&a);
    palind();
    long long rasp=strlen(a);
    for(int i=0; i<n; i++)
        if(i%2)
            rasp+=(lsc[i]-1)/2;
        else
            rasp+=lsc[i]/2;
    printf("%lld",rasp);
    return 0;
}