Cod sursa(job #667589)

Utilizator balakraz94abcd efgh balakraz94 Data 23 ianuarie 2012 13:54:57
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
#include<algorithm>
#define infile "pscpld.in"
#define outfile "pscpld.out"
#define n_max 2000005
using namespace std;

char S[n_max]; 

int Lung[n_max];

int N;

long long sol;


void citeste()
{
	freopen(infile,"r",stdin);
	
	do
	{
		N++;
		scanf("%c",&S[2*N-1]);
		
	}while(S[2*N-1]);
	N--;
	
	fclose(stdin);
}



void rezolva()
{
	int idx = 1;
	
    for (int i=1; i<2*N; ++i)
    {
        if (idx + Lung[idx] - 1 < i)
            Lung[i] = i&1; 
        else
            Lung[i] = min(Lung[idx - (i - idx)], idx + Lung[idx] - i );

        int j = Lung[i] + 1;
		
        while (i - j >= 1 && i + j < 2*N && S[i-j] == S[i+j])
            j+=2;
        j -= 2;
		
        Lung[i] = j + 1;
		
        if ( i + Lung[i] > idx + Lung[idx])
            idx = i;
	
        sol += (Lung[i] + 1) / 2;
    }
}



void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	printf("%lld\n",sol);
	
	fclose(stdout);
}


int main(void)
{
	citeste();
	rezolva();
	afiseaza();
	
    return 0;
}