Cod sursa(job #1168993)

Utilizator MKLOLDragos Ristache MKLOL Data 10 aprilie 2014 01:24:17
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<sstream>
#include<iostream>
#include <iomanip>
#include<cstdlib>
#include<cmath>
#include<cstring>
#define pb push_back

using namespace std;

char s[2010000];
char s1[2010000];
int val[2020201];
int maxind,maxVal,N;
long long S=0;
void make_sir(){

    for(int i=1;i<=N;++i){
        s1[i*2-1]=s[i];
        s1[i*2]='*';
    }
}

int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    scanf("%s",s+1);
    N = strlen(s+1);
    make_sir();
    for(int i=1;i<2*N;++i)
    {
        if(maxVal >= i){
            int loc = maxind - (i-maxind);
            val[i] = min(val[loc],maxVal-i);
        }
        //printf("%c %c %c\n",s1[i],s1[i-val[i]-1],s1[i+val[i]+1]);
        while( (s1[i-val[i]] == s1[i+val[i]]) && (i - val[i] > 0) && (i + val[i] < 2*N)){
            ++val[i];
            if(i + val[i] > maxVal){
                maxVal = i + val[i];
                maxind = i;
            }
        }
    }
    for(int i=1;i<2*N;++i){
        //printf("%d %c\n",val[i],s1[i]);
        S+=(val[i]+1)/2;
        if(s1[i]=='*')
            --S;
    }

    printf("%lld",S);
    return 0;
}