Cod sursa(job #1227500)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 10 septembrie 2014 19:23:44
Problema PScPld Scor 100
Compilator cpp Status done
Runda ubb_acm_2014_etapa_individuala_01 Marime 1.1 kb
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cmath>
#include <fstream>
#include <cstring>
#include <bitset>
#include <stack>
#include <vector>
#include <map>
#include <set>

#define per pair<int,int>
#define x first
#define y second
#define DN 200000
#define DM 2000
using namespace std;

ifstream f("pscpld.in");
ofstream g("pscpld.out");

char C[2000020],A[1000005];
int n,i,k,P[2000020],id=1,mx=2;
long long rez;

void read(){

    f>>A;
    n=strlen(A);
    C[0]='$'; C[1]='#';

    k = 2;

    for(int i=0 ; i<n ; ++i){

        C[k++] = A[i];
        C[k++] = '#';
    }
    C[k]='\0';
}

int main()
{
    read();


    P[1]=1;
    n=strlen(C);

    for(i=2;i<n;i++)
    {
        P[i]= ((mx>i) ? min(P[2*id-i],mx-i):1 );

        while(C[i+P[i]]==C[i-P[i]]) /// extindem palindromul cu centrul in i
            P[i]++;

        if(P[i]+i>mx)
        {
            mx=P[i]+i;
            id=i;
        }
    }

    for(i=1;i<n;i++){

        if(C[i]=='#')
            rez+=(P[i]-1)/2;
        else
            rez+=P[i]/2;
    }

    cout<<rez;
    g<<rez<<'\n';
    return 0;
}