Cod sursa(job #1234297)

Utilizator george_stelianChichirim George george_stelian Data 27 septembrie 2014 00:59:58
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int sol[2000010],n,i,mid,lim;
char v[2000010];
long long rez;

int main()
{
    freopen("pscld.in", "r", stdin);
    freopen("pscld.out", "w", stdout);
    scanf("%s",v+1);
    n=strlen(v+1);
    for(i=n;i;i--)
    {
        v[2*i]=v[i];
        v[2*i-1]='#';
    }
    n=2*n+1;
    v[n]='#';
    mid=lim=1;
    for(i=2;i<=n;i++)
    {
        if(i<=lim) sol[i]=min(sol[mid-(i-mid)],lim-i);
        while(1<=i-sol[i]-1 && i+sol[i]+1<=n && v[i-sol[i]-1]==v[i+sol[i]+1]) sol[i]++;
        if(i+sol[i]>lim)
        {
            lim=i+sol[i];
            mid=i;
        }
    }
    for(i=1;i<=n;i++)
        if(i%2) rez+=(sol[i]+1)/2;
        else rez+=(sol[i]+2)/2;
    printf("%lld",rez);
    return 0;
}