Cod sursa(job #1053954)

Utilizator deividFlorentin Dumitru deivid Data 13 decembrie 2013 01:41:24
Problema PScPld Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<stdio.h>
#include<vector>
#include<unordered_map>
#include<set>
#include<algorithm>
#include<cstring>

#define maxlen 1000005
#define maxn 605
#define maxcif 7005

using namespace std;

char sir[maxlen];
int D[maxlen];

inline void pscpld ( char *sir , int len , int *D , int add = 0 ) {
	
	int st = 1,dr = 0;
	for ( int i = 1 ; i <= len ; ++i ){
		if ( add && sir[i] != sir[i+1] ){
			D[i] = 0; continue ;
		}
		
		if ( i >= dr ){
			st = i,dr = i+add; D[i] = 1;
			while ( st > 1 && dr < len && sir[st-1] == sir[dr+1] ){
				--st; ++dr;
				++D[i];
			}
		}
		else{
			int centre = (st+dr+add)>>1;
			D[i] = min(D[centre+centre-i-add],dr-i+1-add);
			
			int p = i-D[i]+1,u = i+D[i]-1+add;
			while ( p > 1 && u < len && sir[p-1] == sir[u+1] ){
				--p; ++u;
				++D[i];
			}
			
			if ( u > dr )	st = p,dr = u;
		}
	}
}

inline long long getNumberOfPalindroms ( char *sir ){
	int len = strlen(sir+1);
	long long pals = 0;
	
	pscpld(sir,len,D);
	
	for ( int i = 1 ; i <= len ; ++i )	pals += D[i];
	memset(D,0,sizeof(D));
	pscpld(sir,len,D,1);
	for ( int i = 1 ; i <= len ; ++i )	pals += D[i];
	
	return pals;
}

int main () {
	
	//#ifndef ONLINE_JUDGE
	freopen("pscpld.in","r",stdin);
	freopen("pscpld.out","w",stdout);
	//#endif
	
	scanf("%s",sir+1);
	
	long long palindroms = getNumberOfPalindroms(sir);
//	//n = 15; palindroms = 2;
//	fscanf(stdin,"%d %d",&n,&palindroms);
	printf("%lld\n",palindroms);
	
	return 0;
}