3 ms·

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

by foota 4y ago

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.

thdc 4y ago
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.
- ithkuil 4y ago
  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)
  - krackers 4y ago
    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/03/23/string-hashing-and-palindromes.html 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).

by foota 4y ago

thdc 4y ago

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.

ithkuil 4y ago
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)
- krackers 4y ago
  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/03/23/string-hashing-and-palindromes.html 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).