Cod sursa(job #1738279)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 6 august 2016 12:42:18
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
#define NMAX 1000001*2+2
#define MMAX 1000001

ifstream in("pscpld.in");
ofstream out("pscpld.out");

char a[NMAX],v[MMAX];
long long n,c,p[NMAX],m,d,r;
int main()
{
    in >> v;
    n = strlen(v);

    a[0] = '&';
    for(int i=0,k=1;i<n;i++)
    {
        a[k++]='#';
        a[k++] = v[i];
    }
    a[2*n+1]='#',a[2*n+2]='@';

    n=2*n+1;
    p[2] = 1;
    c = 2;
    m = 0;
    r=2;

    for(int i=3;i<n;i++)
    {
        m = 2*c-i;
        if(i<r) p[i] = min(r-i,p[m]);
        else p[i] = 0; //deja 0?
        while(a[i+p[i]+1] == a[i-p[i]-1])
        {
            p[i]++;
        }

        if(i+p[i]>r)
        {
            c = i;
            r = i+p[i];
        }
    }
    long long cnt = 0;
    for(int i=0;i<=n;i++)
    {
   // cout << p[i] << " ";

        if(p[i]%2==0)
            cnt += p[i]/2;
        else
        {
            cnt +=p[i]/2+1;
        }
    }
    out <<cnt;

    return 0;
}