Cod sursa(job #1746220)

Utilizator antanaAntonia Boca antana Data 22 august 2016 21:34:44
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>
#include<string.h>
#define MAXN 1000000

char aux[MAXN+1], s[2*MAXN];
int n, p[2*MAXN], np, ans;

inline int maxim(int a, int b)
{
    if(a>b)
        return a;
    return b;
}

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

    int r=0, c=0;

    gets(aux);
    n=strlen(aux);

    s[0]='*';
    for(int i=0;i<n;++i)
        s[2*i+1]=aux[i], s[2*i+2]='*';
    np=2*n;

    for(int i=1;i<=np;++i)
    {
        if(i>r) p[i]=0;
        else
        {
            if(p[2*c-i] > r-i)
                p[i]=r-i;
            else p[i]=p[2*c-i];
        }
        while(i+p[i]+1 <=np && i-p[i]-1 >=0 && s[i+p[i]+1]==s[i-p[i]-1])
            p[i]++;

        if(i+p[i] > r)
        {
            r=i+p[i];
            c=i;
        }
        ans+=(p[i]+1)/2;
    }
    printf("%d", ans);

    return 0;
}