WA in SPOJ EPALIN

general
, ,
1

hi! can anyone help me. i got WA in http://www.spoj.com/problems/EPALIN/
i have tried and optimised as much as i could.
i tried it with these test cases:-
abcdefglananahijklmnopqrstananal
laxalghijklaxal
jklaxalghijklaxal

any help would be appreciated :slight_smile: (any different test case or hint)

CODE:-

2

@harindersingh ,
for input string : aaabcdxxxx , your output is : aaabcdxxxxdcbaaa i.e. printing an extra ‘x’ as correct output is : aaabcdxxxdcbaaa .

3

i think according to the problem statement characters can be only added and not deleted.
if it has to display aaabcdxxxdcbaaa, it’ll have to delete 1 x from the end of original string

4

thanks harinder singh

5

Hello all.
Got Ac with this simplest implemenation for this problem :smiley:


#include 
using namespace std ;
#define ULL unsigned long long 
#define MAXN 200015

char str[MAXN] ;
int N ;
ULL hashF[MAXN] , hashB[MAXN] , P , POW[MAXN];


void process(){

	P = 37 ;
	hashF[0] = 0 ;
	hashB[N+1] = 0 ;
	POW[0] = 1 ;
	for(int i=1;i<=N;i++){
		hashF[i] = hashF[i-1]*P + (str[i]) ;
		POW[i] = POW[i-1]*P ;	
	}

	for(int i=N;i>=1;i--){
		hashB[i] = hashB[i+1]*P + (str[i]) ;
	}
}

int main(){


	while(scanf("%s",str+1) != EOF){

		N = strlen(str+1) ;
		process() ;
		int len = N ;
		for(int i=1;i<=N;i++){	
			ULL hash1 = hashF[N]-hashF[i-1]*POW[len] ;
			ULL hash2 = hashB[i];	
			if(hash1 == hash2){
				break ;
			}
			len -- ;
		}
		int need = N-len ;
		str[need+N+1] = 0 ;
		int low = 1 ;
		int high = N+need ;
		while(low <= high){
			str[high] = str[low] ;
			high -- ;
			low ++ ;
		}
		printf("%s\n",str+1) ;
	}
	return 0 ;
}
1 Like
6

Hello ma5termind

But there is no surity as colloision may take place in this method. how to make sure that collision never occurs ?

Thanks