Cod sursa(job #1003451)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 30 septembrie 2013 19:13:21
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <cstring>

using namespace std;

char sir[2000010];
int man[2000010];
char init[1000005];

int main()
{
    ifstream cin("pscpld.in");
    ofstream cout("pscpld.out");

    cin.get(init,1000005);
    int n=strlen(init),dif,i,centru=0;
    long long int s=0;
    for(i=n; i>=1; i--)
        init[i]=init[i-1];
    for(i=1;i<=n;i++)
    {
        sir[2*i-1]='*';
        sir[2*i]=init[i];;
    }
    sir[2*n+1]='*';
    n*=2;
    n++;
    for(i=1; i<=n; i++)
    {
        if((centru+man[centru])<i)
            dif=1;
        else if((2*centru-i-man[2*centru-i])>(centru-man[centru]))
        {
            man[i]=man[2*centru-i];
            //cout<<man[i]<<' ';
            s+=(man[i]/2);
            if(sir[i]!='*')
                s++;
            continue;
        }
        else
            dif=2*centru-i-(centru-man[centru])+1;
        for(; ((i-dif)>=1) && ((i+dif)<=n) && dif<n; dif++)
            if(sir[i+dif]!=sir[i-dif])
                break;
        man[i]=dif-1;
        if((i+man[i])>(centru+man[centru]))
            centru=i;
        //cout<<man[i]<<' ';
        s+=(man[i]/2);
        if(sir[i]!='*')
            s++;

    }
    cout<<s<<'\n';
    cin.close();
    cout.close();
    return 0;
}