Cod sursa(job #916722)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 16 martie 2013 20:17:43
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;

#define NMAX 2000005

char s[NMAX],t[NMAX];
int p[NMAX],n;

void compute_t()
{
	int i;
	t[0]='1';
	for(i=1;i<=n;i++) {
		t[2*i-1]='#';
		t[2*i]=s[i];
	}
	t[2*n+1]='#';
	t[2*n+2]='2';
	n=2*n+2;
}

void manacher()
{
	int R,C,i,j;
	compute_t();
	R=1;
	C=1;
	for(i=2;i<=n-1;i++) {
		j=2*C-i;
		if(i+p[j]<R)
			p[i]=p[j];
		else {
			p[i]=R-i;
			while(t[i+p[i]+1]==t[i-p[i]-1])
				p[i]++;
		}
		if(i+p[i]>R) {
			R=p[i]+i;
			C=i;
		}
	}
}

int main ()
{
	
	int i;
	long long nr;
	ifstream f("pscpld.in");
	ofstream g("pscpld.out");
	f>>(s+1);
	f.close();
	n=strlen(s+1);
	manacher();
	nr=0;
	for(i=1;i<=n-1;i++)
		nr=0LL+nr+p[i]/2+1;
	g<<nr-(n-2)/2-1;
	g.close();
	return 0;
}