Same algorithm but replaced palindromic checking by hashing (use int64 hash range):
for (int j=i; j < n; ++j) {
h=31*h+s[j];
hR=hR+p*s[j];
p*=31;
if ((j-i)%2==1 && h==hR) {
cont=true;
i=j+1;
break;
}
}
Saturday, October 31, 2009
[SPOJ] PALDR (Solved)
PALDR Solved
Same algorithm but replaced palindromic checking by hashing (use int64 hash range):
Same algorithm but replaced palindromic checking by hashing (use int64 hash range):
Subscribe to:
Post Comments (Atom)
Hello, I have used a similar approach, finding smallest even palindrome from position i and then jumping to i + len(palindrome at i) and continuing this process. But I got wrong answer in this problem. Can you tell me what might go wrong? Thanks and nice blog.
ReplyDelete