Cod sursa(job #912622)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 12 martie 2013 17:01:18
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
FILE *f=fopen("pscpld.in","r"),*g=fopen("pscpld.out","w");
int x[2000005],i,j,k,centru;
char aux[1000005],s[2000005];
long long ras;
int main()
{
    fgets(aux,1000005,f);
    int n=strlen(aux),N=-1;
    for(i=0;i<n;i++)
    {
        s[++N]='#';
        s[++N]=aux[i];
    }
    for(i=1,j=0;i<=N;i++)
    {
        if(i>j)
        {
            for(k=1;i+k<=N&&s[i+k]==s[i-k];k++);
            x[i]=k-1;
            j=i+k-1;
            centru=i;
        }
        else
        {
            if(x[2*centru-i]<j-i)
                x[i]=x[2*centru-i];
            else
            {
                for(k=1;j+k<=N&&s[j+k]==s[2*i-j-k];k++);
                x[i]=j-i+k-1;
            }
            if(j<i+x[i])
            {
                j=i+x[i];
                centru=i;
            }
        }
        ras+=(x[i]+1)/2;
    }
    fprintf(g,"%lld\n",ras);
    return 0;
}