Cod sursa(job #712804)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 13 martie 2012 20:13:39
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<fstream>
#include<algorithm>
#define n_max 999999999
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char S[n_max]; 

int Lung[n_max];

int N;

long long sol;


void citeste()
{
	
    while (fin >> S[2 * N + 1])
        N ++;
	
    fin.close();
}



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()
{
	
	fout<<sol<<'\n';
	
	fout.close();
}


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