[HN Gopher] Palindromic Rolling Hash (2016) ___________________________________________________________________ Palindromic Rolling Hash (2016) Author : weird_user Score : 17 points Date : 2023-01-17 12:01 UTC (3 days ago) (HTM) web link (aleclownes.com) (TXT) w3m dump (aleclownes.com) | thdc wrote: | > 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. | krackers wrote: | 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. ___________________________________________________________________ (page generated 2023-01-20 23:00 UTC)