Cod sursa(job #1053943)

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

#define maxlen 100005
#define maxn 605
#define maxcif 7005

using namespace std;

char sir[maxlen];
int n;
int D[maxlen],H[maxlen][3],power[maxlen][3];
int phi[maxn];
int N[maxcif],aux[maxcif];

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-1],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 int getNumberOfPalindroms ( char *sir ){
	int len = strlen(sir+1);
	int pals = 0;
	
	pscpld(sir,len,D);
	
	for ( int i = 1 ; i <= len ; ++i )	pals += D[i];
	
	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);
	
	int palindroms = getNumberOfPalindroms(sir);
//	//n = 15; palindroms = 2;
//	fscanf(stdin,"%d %d",&n,&palindroms);
	printf("%d\n",palindroms);
	
	return 0;
}