Cod sursa(job #790186)

Utilizator veleanduAlex Velea veleandu Data 20 septembrie 2012 17:08:12
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
// de la ce vine pscpld?
#include <cstdio>
#include <string.h>
using namespace std;
#define maxn 100005
#define min(a,b) ((a<b)?(a):(b))

    char Text[2*maxn];
    long R[2*maxn];
    long n,i,last;
    long long Rez;

int main()
{
    freopen ("pscpld.in","r",stdin);
    freopen ("pscpld.out","w",stdout);
    scanf ("%s", (&Text) );
    n=strlen(Text);
    n--;
    for ( i= 2*(n+1); i>=0; i-- )
         if ( (i&1) )
            Text[i] = Text[ (i>>1) ];
        else
            Text[i] = '*';
    n++;
    n*=2;
    for ( i=0; i<=n; i++ )
    {
        if ( R[last]+last >=i )
            R[i] = min ( R[last]+last-i , R[2*last-i] );
        while ( ( Text[ i-R[i]-1 ] == Text[ i+R[i]+1 ] )
               && ( i-R[i]-1 >= 0)
               && ( i+R[i]+1 <= n) )
                R[i]++;
        Rez+=( R[i] + (i&1) )>>1;
        if ( i+R[i] > last+R[last] )
            last=i;
    }
    printf("%lld", Rez);
    return 0;
}