Palindromic Rolling Hash (2016) | Hacker News Reader

Palindromic Rolling Hash (2016)

aleclownes.com

26 pointsweird_user8 comments

It's not novel (I've seen this approach discussed before in competitive programming circles), but it's certainly not too well known. Generally, preprocessing strings via rolling hashes allows you to comparisons in "constant" time.

> A palindrome check on this object will take O(1) time for false and O(n) time for true.

Someone correct me if I'm wrong, but this sounds like a suspicious statement to me. If the false case is constant time, then the true (not false) case should also be constant time. In reality, I think the statement should be something like "the palindrome check runs in O(n) time", but that may ruin the overall runtime by my understanding.

I have not looked closely at the implementation.

Ok, I thought about it some more and I think the usage of Big-O in that sentence is what confused me. The comparison of two hashes is constant time is my takeaway. The key point of this approach is that it replaces the linear string comparison with the comparison of rolling hashes if I understand correctly, which makes it faster. Sounds relatively unique - as in a nice approach that's non-textbook.

I believe this kind of thinking is what these kinds of interviewing questions are supposed to look for, rather than regurgitating memorized answers (and pretending you came up with them). But the difficulty spiked due to people gaming the interview which ruined it for the normal non-leetcode-prep engineers.

I think they're saying that you can conclusively say two strings are different in constant time, but it requires O(length of string) to confirm that two strings really are the same since there can be hash collisions.

So the runtime depends on the frequency of hash collisions. You could construct an adversarial input where there would be many collisions and that would not run in linear time, but the average expected runtime over random inputs can still be O(n).

I wonder if some of the approaches that are used to make hash tables collision could be applied here to make it linear in the presence of adversarial input distribution?

Edit: Maybe if you could update the rolling hash in constant time to account for the distance of each element from the center? Seems like that might not be possible though...

Edit: Hm, that wouldn't work though, since (obviously) if the text is all the same then you must have two two values the same if they are equal.

Edit: To flip the problem a bit, I'm not sure it's possible to construct an adversarial input that is adversarial everywhere but also not trivially a palindrome. So maybe you could assume that all collisions are actually equal, and then backtrack at the end based on whether the collision really wasn't a palindrome? This wouldn't work if constructing adversarial non-trivial inputs is possible, but it seems at least like a somewhat hard problem.

Interesting, I didn't consider the hash collision angle, as I figured they're normally rare enough to discard as part of average runtime calculations.

It does seem to line up with the explanation of the algorithm though - the less candidate palindromes the better as it enters the linear runtime branch less often.

I'm not well versed on hash collisions but I imagine it's kind of awkward to do in this scenario - the strings will have to initially be palindromes themselves to get to a decent length to scale the comparison's runtime (why compare str1 + x and str2 + y when str1 and str2 don't match). As posted towards the end of tfa, an example worst case in put is something like aaaaaaaaaaaaaa.

Unless you want your algorithm to produce wrong results sometimes, you have to check whether two strings are sctually equal even if you know they are really likely to br equal (since they hash to the same value)

That's true, but practically when you do this you can just say the probability of a false positive is bounded above by 1/1e5 or so and you just ignore it, because most likely the only reason you care about the longest palindromic substring in the first place is to pass the leetcode autograder.

Edit: For a more rigorous proof of the error bound, see https://baites.github.io/algorithms/algorithm-analysis/2020/...

Basically it's O(n)/P where P is your prime modulus (usually 1e6 + 3 or 1e9 + 9), so for most practical input lengths your probability of collision is negligibly small enough that you'll pass the autograder).

If you use binary search on the length of the substring then you can get to n log(n) expected time, independent of the input distribution.

Right, the two approach I've seen are 1) either go through each possible (n-1) palindrome centers and for each binary search to find the longest palindrome at that center. Or 2) Since for a given length L we can find if there exists a length L palindromic substring in O(n) time, we then binary search on L. The former has an advantage in that you can immediately answer the number of palindromic substrings as well, although it's a bit harder to implement in terms of edge-cases you need to worry about.

Reply on news.ycombinator.com