Cod sursa(job #1295711)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 20 decembrie 2014 01:01:11
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define N 1000100

char ch[N],v[2*N];
long long distanta[2*N];

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

    register long long h=0,len,suma=0,k;
    register long long imax=1,lgmax=1;

    scanf("%s",ch+1);
    len = strlen(ch+1);

    v[0] = '!';  v[2*len] = '@'; h = len*2; distanta[1] = 1;

    for(int i = 1; i <=len;++i) v[i*2-1] = ch[i];

    for(register int i=1;i <= h;++i){
        distanta[i] = min( imax + lgmax- i, distanta[2*imax-i] ) ;
        k = distanta[i];
        while( v[i - k ] == v[ i+ k ])  ++k;
        distanta[i] = k;
        if( i + distanta[i] > imax + lgmax )  imax = i  ,  lgmax = distanta[i];
    }

    for(register int i = 1;i < h ; i+=2) suma += (distanta[i]+1)/2;
    for(register int i = 2;i < h ; i+=2) suma +=  distanta[i]   /2;
    printf("%lld",suma);

    return 0;
}