Cod sursa(job #230435)

Utilizator crawlerPuni Andrei Paul crawler Data 13 decembrie 2008 22:04:58
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <stdio.h>

#define Nmax 2000100

int n,l[Nmax];
char x[Nmax/2],v[Nmax];

int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    
    fgets(x,Nmax,stdin);
    
    n = 1;
    v[1] = ' ';
    
    for (int i=0;x[i] >= 'a' && x[i] <= 'z';++i)
    {
        v[++n] = x[i];
        v[++n] = ' ';
    }
    
    //printf("%s\n", v+1);
    
    int st=1, dr=3;
    l[2] = 1;
    
    for (int i=3;i<=n;++i)
    {
        if (i<=dr)
        {
             int poz = dr-i;
             if (i+l[st+poz] >= dr)
             {
                l[i] = dr-i;
                st = i - l[i];
                dr = i + l[i];
                while (v[st-1] == v[dr+1] && st > 1)
                {
                     --st;
                     ++dr;
                     ++l[i];      
                }                                  
             } 
                else    
             l[i] = l[st+poz];
        }    
             else
        {
             l[i] = 0;
             st = i;
             dr = i;
             while (v[st-1] == v[dr+1] && st > 1)
             {
                   --st;
                   ++dr;
                   ++l[i];      
             }     
        }
    }
    
    long long ret = 0;
    
    for (int i=1;i<=n;++i)
    if (v[i] == ' ') ret += (l[i]+1)/2;
    else ret += 1 + (l[i]/2);
    
    printf("%lld\n",ret);    
    
    return 0;    
}