Cod sursa(job #2289061)

Utilizator ana.pintiliciucAna Maria Pintiliciuc ana.pintiliciuc Data 24 noiembrie 2018 10:51:54
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>
#include <algorithm>

using namespace std;

char a[2000005];
int p[2000005], sim[2000005];

int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    int ok=0, n, i;
    for(i=0;ok==0;i++)
    {
        if(i%2==1)
        {
            char c;
            scanf("%c", &c);
            if(c>='a' && c<='z')
                a[i]=c;
            else ok=1;
        }
        else a[i]='#';
    }
    n=i-1;
    int c=0, r=0, pal=0;
    for(i=1;i<=n-1;i++)
    {
        ok=0;
        sim[i]=c-(i-c);
        p[i]=0;
        if(r>i)
            p[i]=min(r-i, p[sim[i]]);
        while(a[i+1+p[i]]==a[i-1-p[i]])
        {
            ok=1;
            p[i]=p[i]+1;
        }
        if(i+p[i]>r)
        {
            r=i+p[i];
            c=i;
        }
        if(ok==1)
            pal+=p[i];
    }
    printf("%d", pal);

    return 0;
}