[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)