Cod sursa(job #1068895)

Utilizator sebinechitasebi nechita sebinechita Data 28 decembrie 2013 21:56:59
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
#define MAX 1001000
#define mx id+p[id]
char a[MAX], s[2*MAX+1];
int p[2*MAX+1];
int i, S;
int main()
{
    fin>>a;
    s[0]='&';
    s[1]='#';

    for(i=0;a[i]!='\0';i++)
    {
        s[2*i+2]=a[i];
        s[2*i+3]=s[1];

    }
    int id=0;
    p[id]=0;
    for(i=1;s[i]!='\0';i++)
    {
        if(mx-i>0)
        {
            if(mx-i>=p[2*id-i])
            {
                p[i]=p[2*id-i];
            }
            else
                p[i]=mx-i;
        }
        else
        {
            p[i]=1;
        }
        while(s[i+p[i]]==s[i-p[i]])
        {
            p[i]++;
        }
        if(i+p[i]>mx)
            id=i;
    }

    for(i=1;s[i]!='\0';i++)
    {
        S+=p[i]/2;
    }
    fout<<S;
}