Cod sursa(job #1883893)

Utilizator Vlad1111Sbengheci Vlad-Andrei Vlad1111 Data 18 februarie 2017 11:53:23
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream>
#include <cstdio>
#include <string.h>
#define cout cerr
#define MAX 1000003 * 2
using namespace std;

char a[MAX],x;
int n=1,R,C;
int pal[MAX];
long long S;

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

    /*a[n++]='#';
    while(!feof(stdin))
    {
        scanf("%c",&x);
        if(x>='a' && x<='z')
        {
            a[n++]=x;
            a[n++]='#';
        }
    }*/
    scanf("%s",a+2);

    n=strlen(a+2);
    n=2*n+2;
    pal[1]=0;
    pal[2]=1;
    C=2,R=3;
    S=1;
    for(int i=3;i<n;i++)
    {
        int ii=2*C-i;
        if(pal[ii]+i<R)
            pal[i]=pal[ii];
        else
        {
            pal[i]=R-i;
            if(pal[i]<0)
                pal[i]=0;
        }

        //cout<<i<<" "<<C<<" "<<R<<" "<<pal[i]<<endl;
        while(pal[i]+i+1<n && i-pal[i]-1>0)
            if((pal[i]+i+1)%2==1)
                pal[i]++;
            else if(a[(i-pal[i]-1)/2+1]==a[(i+pal[i]+1)/2+1])
                pal[i]++;
            else break;

        if(i+pal[i]>=R)
        {
            C=i;
            R=pal[i]+i;
        }
        S+=(pal[i]+1)/2;
    }
    //cout<<endl;
    /*cout<<"# ";
    for(int i=2;i<=n/2;i++)
        cout<<a[i]<<" # ";
    cout<<endl;
    for(int i=1;i<n;i++)
        cout<<pal[i]<<" ";
        cout<<endl;*/
    printf("%d",S);
    return 0;
}