Cod sursa(job #1883706)

Utilizator Vlad1111Sbengheci Vlad-Andrei Vlad1111 Data 18 februarie 2017 10:18:12
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <cstdio>
#define cout cerr
#define MAX 200002
using namespace std;

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

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

    a[n++]='#';
    while(!feof(stdin))
    {
        scanf("%c",&x);
        if(x>='a' && x<='z')
        {
            a[n++]=x;
            a[n++]='#';
        }
    }
    pal[1]=0;
    pal[2]=1;
    C=1,R=1;
    for(int i=3;i<n;i++)
    {
        int l=i-C;
        int ii=2*C-i;
        if(pal[ii]<R-i)
            pal[i]=pal[ii];
        else
        {
            pal[i]=0;
            while(pal[i]+i+1<n && i-pal[i]-1>0
                  && a[pal[i]+i+1]==a[i-pal[i]-1])
                pal[i]++;
        }
        if(l>=R)
        {
            C=i;
            R=pal[C];
        }
        //cout<<C<<" "<<R<<endl;
    }
    /*cout<<endl;
    for(int i=1;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    for(int i=1;i<n;i++)
        cout<<pal[i]<<" ";*/
    for(int i=1;i<n;i++)
        if(pal[i]>1)
            S+=pal[i]-1;
        else S+=pal[i];

    //cout<<endl;
    //cout<<S;
    printf("%d",&S);
    return 0;
}