Cod sursa(job #667660)

Utilizator balakraz94abcd efgh balakraz94 Data 23 ianuarie 2012 16:33:07
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 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 Lg[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 + Lg[idx] - 1 < i)
            Lg[i] = i&1;
        else
            Lg[i] = min(Lg[idx - (i - idx)], idx + Lg[idx] - i);

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



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


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