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
(any different test case or hint)
CODE:-
@harindersingh ,
for input string : aaabcdxxxx , your output is : aaabcdxxxxdcbaaa i.e. printing an extra βxβ as correct output is : aaabcdxxxdcbaaa .
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
Hello all.
Got Ac with this simplest implemenation for this problem 
#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
Hello ma5termind
But there is no surity as colloision may take place in this method. how to make sure that collision never occurs ?
Thanks