Cod sursa(job #578664)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 11 aprilie 2011 14:45:57
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#define Nmax 1000003
#define LL long long
using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

char s[Nmax];
int lg[2][Nmax];
int N;

inline int Minim(int x,int y){ return x<y ? x:y ; }

int main(){
    int i,j,dist,dcc,cc,cc2,st,dr,is,id; LL sol;
    fin>>s+1;
    for(N=1; s[N]>='a' && s[N]<='z'; ) ++N;
    --N;

    dr=0; cc=0;
    for(i=1;i<=N;++i){
        // impar
        if( dr>=i ){
            dist=(dr-i+1)*2-1;
            dcc=i-cc;
            st=cc-dcc+(cc2!=0);
        }
        else st=i, dist=1,lg[0][i]=1;

        lg[0][i]=Minim(lg[0][st],dist);
        if( lg[0][i] && lg[0][i]%2==0 ) lg[0][i]--;

        for( is=i-lg[0][i]/2-1, id=i+lg[0][i]/2+1; is>=1 && id<=N &&s[is]==s[id]; --is,++id )
            lg[0][i]+=2;
        id--;
        if( id>dr ) dr=id, cc=i, cc2=0;

        // par
        if( s[i]!=s[i+1] ) continue;
        if( dr>=i+1 ){
            dist=(dr-(i+1)+1)*2;
            dcc=(i+1)-cc;
            st=cc-dcc+(cc2!=0);
        }
        else st=i, dist=2, lg[1][i]=2;

        lg[1][i]=Minim(lg[1][st],dist);
        if( lg[1][i]&1 ) lg[1][i]--;

        for( is=i-lg[1][i]/2, id=i+1+lg[1][i]/2; is>=1 && id<=N &&s[is]==s[id]; --is,++id )
            lg[1][i]+=2;
        id--;
        if( id>dr ) dr=id, cc=i, cc2=i+1;
    }

    sol=0;
    for(i=1;i<=N;++i)
        sol+=1LL*(lg[0][i]+1)/2+1LL*lg[1][i]/2;

    fout<<sol<<"\n";
    fin.close(); fout.close();
    return 0;
}