Hashing

String hashing is a powerful technique that converts a string into a numerical value (a hash) of a fixed size. This allows for constant-time average comparisons of strings. While hash collisions (different strings producing the same hash) can occur, they are rare with good hash functions and can be handled. The most common and effective method is polynomial rolling hash. A string `S = s1s2...sn` is treated as a polynomial in a base `p`, evaluated modulo `m`. The hash is calculated as `(s1*p^0 + s2*p^1 + ... + sn*p^(n-1)) mod m`. The values `p` and `m` are chosen carefully: `p` should be a prime number larger than the size of the alphabet, and `m` should be a large prime number to minimize collisions. The 'rolling' aspect, as seen in Rabin-Karp, allows us to compute the hash of any substring in O(log n) time (for modular inverse) or O(1) if we precompute powers of `p` and their inverses. This technique is incredibly versatile. It can be used to check if two substrings are identical, find the longest repeated substring, or even check for palindromes. To check if a substring `S[i...j]` is a palindrome, we can compute its hash and the hash of its reversed version. This requires computing hashes of reversed prefixes, which can also be done efficiently with precomputation. String hashing provides a simple and fast alternative to more complex algorithms for many problems.