45:"/_next/static/chunks/33yus346z0l_n.js" 46:"/_next/static/chunks/2j22cxchii_xx.js" 47:"/_next/static/chunks/0iv56yrji_20j.js" 48:"/_next/static/chunks/32izpn90gvm22.js" 49:"/_next/static/chunks/3j8bi-zu9bqs4.js" 4a:"/_next/static/chunks/1z-pox7hqp2x3.js" 4b:"/_next/static/chunks/20w4eaqlekefm.js" 4c:"/_next/static/chunks/1tn-0fivsxsv1.js" 4d:"/_next/static/chunks/09nq57stwzkgf.js" 4e:"/_next/static/chunks/3m1xjj5kw5fie.js" 4f:"/_next/static/chunks/0gafyzg9j9yqj.js" 50:"/_next/static/chunks/3k2gyg36fnag_.js" 51:"/_next/static/chunks/3bgoyiso1rhn7.js" 52:"/_next/static/chunks/3cstd6xzfli_o.js" 53:"/_next/static/chunks/253gnmj0-cj17.js" 54:"/_next/static/chunks/0hlb44ca7-4a2.js" 55:"/_next/static/chunks/20329i6m_04t6.js" 56:"/_next/static/chunks/40mq7ggq-ozo4.js" 57:"/_next/static/chunks/082jo-0ajazgr.js" 58:"/_next/static/chunks/2ozcrjb_hh74t.js" 59:"/_next/static/chunks/01a-3hvnqu8wl.js" 5a:"/_next/static/chunks/05i8en-x14ibi.js" 5b:"/_next/static/chunks/3m0r7x0jt5wm7.js" 5c:"/_next/static/chunks/2k8pepwc4pxns.js" 5d:"/_next/static/chunks/0wa9m1-tphf9u.js" 5e:"/_next/static/chunks/30jdm3dwz834g.js" 5f:"/_next/static/chunks/0k9bl6dipnsvu.js" 60:"/_next/static/chunks/18ggtgz2yf759.js" 61:"/_next/static/chunks/0i3-eynrkvqi7.js" 62:I[593304,["$2a","$2b","$2c","$2d","$2e","$2f","$45","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61"],"OwnedHydration"] 63:T400,def polynomial_hash(s: str, base: int = 31, mod: int = 10**9 + 7) -> int: """ Compute the polynomial hash of a string. The hash is computed as: H(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-1] * base^0 We use Horner's method for efficient computation: H(s) = ((s[0] * base + s[1]) * base + s[2]) * base + ... Time Complexity: O(n) where n = len(s) Space Complexity: O(1) """ h = 0 for char in s: # Horner's method: multiply previous by base, add new character h = (h * base + ord(char)) % mod return h # Example usage print(f"Hash of 'cat': {polynomial_hash('cat')}") # 98262 print(f"Hash of 'act': {polynomial_hash('act')}") # 96402 print(f"Hash of 'cat' again: {polynomial_hash('cat')}") # 98262 (deterministic) # Demonstrating collision resistance words = ['hello', 'world', 'olleh', 'dlrow', 'cat', 'tac'] hashes = {word: polynomial_hash(word) for word in words} for word, h in hashes.items(): print(f" '{word}' -> {h}")64:Te90,class RollingHash: """ A rolling hash implementation for efficient substring hashing. This class allows computing hash values for all substrings of a fixed length in O(n) total time, by updating the hash incrementally. """ def __init__(self, base: int = 31, mod: int = 10**9 + 7): self.base = base self.mod = mod self.power = 1 # Will hold base^(window_size - 1) def compute_initial_hash(self, s: str, window_size: int) -> int: """ Compute the hash of the first window and prepare the power multiplier. Time Complexity: O(window_size) """ self.window_size = window_size h = 0 # Compute hash using Horner's method for i in range(window_size): h = (h * self.base + ord(s[i])) % self.mod # Precompute base^(window_size - 1) for rolling self.power = 1 for _ in range(window_size - 1): self.power = (self.power * self.base) % self.mod return h def roll(self, current_hash: int, old_char: str, new_char: str) -> int: """ Roll the hash window: remove old_char from the left, add new_char to the right. Time Complexity: O(1) Formula: H(i+1) = (H(i) - old * base^(m-1)) * base + new """ # Remove contribution of old (leftmost) character h = (current_hash - ord(old_char) * self.power) % self.mod # Shift left (multiply by base) and add new (rightmost) character h = (h * self.base + ord(new_char)) % self.mod # Handle negative modulo (Python handles this, but explicit for clarity) return h if h >= 0 else h + self.mod def find_all_substring_hashes(text: str, window_size: int) -> list[int]: """ Compute the hash of every substring of given length. Time Complexity: O(n) where n = len(text) Space Complexity: O(n - window_size + 1) for the result """ if len(text) < window_size: return [] rh = RollingHash() hashes = [] # Compute initial hash current_hash = rh.compute_initial_hash(text, window_size) hashes.append(current_hash) # Roll through the rest of the text for i in range(len(text) - window_size): current_hash = rh.roll( current_hash, text[i], # Character leaving the window text[i + window_size] # Character entering the window ) hashes.append(current_hash) return hashes # Example: Find all occurrences of pattern in text using rolling hash def rabin_karp_search(text: str, pattern: str) -> list[int]: """ Find all occurrences of pattern in text using Rabin-Karp algorithm. Time Complexity: O(n + m) average, O(nm) worst case """ n, m = len(text), len(pattern) if m > n: return [] rh = RollingHash() # Compute pattern hash pattern_hash = rh.compute_initial_hash(pattern, m) rh_text = RollingHash() text_hash = rh_text.compute_initial_hash(text, m) occurrences = [] for i in range(n - m + 1): if i > 0: text_hash = rh_text.roll(text_hash, text[i - 1], text[i + m - 1]) # If hashes match, verify with actual string comparison if text_hash == pattern_hash: if text[i:i + m] == pattern: # Guard against collisions occurrences.append(i) return occurrences # Demonstration text = "abracadabra" pattern = "abra" print(f"Text: '{text}'") print(f"Pattern: '{pattern}'") print(f"Found at positions: {rabin_karp_search(text, pattern)}") # [0, 7]65:Tfc5,class StringHasher: """ A string hasher that supports O(1) substring hash queries after O(n) preprocessing. This is the preferred approach when you need to query many arbitrary substrings of the same string. """ def __init__(self, s: str, base: int = 31, mod: int = 10**9 + 7): """ Precompute prefix hashes and powers. Time Complexity: O(n) Space Complexity: O(n) """ self.s = s self.base = base self.mod = mod self.n = len(s) # prefix_hash[i] = hash of s[0..i-1] (first i characters) # prefix_hash[0] = 0 (empty string) self.prefix_hash = [0] * (self.n + 1) # power[i] = base^i mod M self.power = [1] * (self.n + 1) # Build prefix hashes using Horner's method for i in range(self.n): self.prefix_hash[i + 1] = ( self.prefix_hash[i] * self.base + ord(s[i]) ) % self.mod # Precompute powers of base for i in range(1, self.n + 1): self.power[i] = (self.power[i - 1] * self.base) % self.mod def get_hash(self, left: int, right: int) -> int: """ Get the hash of substring s[left..right] (0-indexed, inclusive). Time Complexity: O(1) This uses the formula: H(s[l..r]) = prefix_hash[r+1] - prefix_hash[l] * base^(r-l+1) """ length = right - left + 1 # Subtract the prefix contribution (scaled appropriately) result = ( self.prefix_hash[right + 1] - self.prefix_hash[left] * self.power[length] ) % self.mod # Handle negative modulo return result if result >= 0 else result + self.mod def compare_substrings( self, l1: int, r1: int, l2: int, r2: int ) -> bool: """ Compare two substrings s[l1..r1] and s[l2..r2] using hashes. Returns True if they are equal (with high probability). Note: False positives are possible due to hash collisions. Time Complexity: O(1) """ if r1 - l1 != r2 - l2: # Different lengths must be different return False return self.get_hash(l1, r1) == self.get_hash(l2, r2) # Example: Find the longest repeated substring using binary search + hashing def longest_repeated_substring(s: str) -> str: """ Find the longest substring that appears at least twice. Uses binary search on length + rolling hash for O(n log n) average time. """ if len(s) <= 1: return "" hasher = StringHasher(s) n = len(s) def has_repeated_of_length(length: int) -> int: """Check if there's a repeated substring of given length. Returns starting index if found, -1 otherwise.""" seen = {} for i in range(n - length + 1): h = hasher.get_hash(i, i + length - 1) if h in seen: # Verify to guard against collision if s[i:i+length] == s[seen[h]:seen[h]+length]: return i seen[h] = i return -1 # Binary search for the longest length left, right = 1, n - 1 result = "" while left <= right: mid = (left + right) // 2 idx = has_repeated_of_length(mid) if idx != -1: result = s[idx:idx + mid] left = mid + 1 # Try longer else: right = mid - 1 # Try shorter return result # Demonstration s = "banana" print(f"String: '{s}'") print(f"Longest repeated substring: '{longest_repeated_substring(s)}'") # 'ana' hasher = StringHasher(s) print(f" Hash queries:") print(f" Hash of 'ban' (0..2): {hasher.get_hash(0, 2)}") print(f" Hash of 'ana' (1..3): {hasher.get_hash(1, 3)}") print(f" Hash of 'ana' (3..5): {hasher.get_hash(3, 5)}") print(f" Substrings equal? {hasher.compare_substrings(1, 3, 3, 5)}") # True43:["$","$L62",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792303949479,"state":{"data":{"json":{"id":"seed_aeccde5fccc78bf3a22adc4cb4ee0e03","slug":"string-hashing-techniques","category":"Data Structures & Algorithms","topic":"String Hashing Techniques","title":"String Hashing Techniques","description":"Master the art of string hashing—a powerful technique that enables efficient pattern matching, duplicate detection, and similarity comparisons. Learn polynomial rolling hashes, optimal parameter selection, collision handling strategies, and applications that extend far beyond simple string matching.","difficulty":"INTERMEDIATE","estimatedMinutes":90,"pages":[{"id":"seed_a5b1dab7620037bc3fafd79813447793","title":"Polynomial Rolling Hash","order":0,"content":[{"id":"opening-hook","title":"The Power of Fingerprinting Strings","content":[{"data":{"content":"Imagine you need to find all occurrences of a pattern within a massive text file—say, searching for a specific DNA sequence in the human genome (approximately 3 billion characters). The naive approach of comparing character-by-character at every position would require trillions of operations. But what if you could represent any string as a single number and compare numbers instead of strings?\n\nThis is the fundamental insight behind **string hashing**: transform strings into numerical fingerprints (hash values) that can be compared in constant time. The magic lies in **polynomial rolling hashes**, a technique that not only computes these fingerprints efficiently but also allows us to update them incrementally as we slide through a text—turning what could be an O(n × m) operation into an O(n + m) average-case operation."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will deeply understand how polynomial hashing works mathematically, why polynomials provide excellent distribution properties, how to compute hash values incrementally in O(1) time per position, and the theoretical foundation that makes rolling hashes so powerful for string algorithms.","variant":"info"},"type":"callout"}]},{"id":"hash-function-concept","title":"The Hash Function Concept","content":[{"data":{"content":"Before diving into polynomial hashes specifically, let's establish what we need from a string hash function and why most simple approaches fail.\n\n**The Goal:**\n\nA hash function H maps strings to integers: H: Σ* → {0, 1, ..., M-1}\n\nwhere Σ is our alphabet and M is the size of our hash space. We want this function to have several properties:\n\n1. **Deterministic**: The same string always produces the same hash value\n2. **Efficient**: Computing H(s) should be fast—ideally O(|s|) time\n3. **Uniform distribution**: Different strings should map to different hash values as evenly as possible\n4. **Incremental computation**: We should be able to update the hash efficiently when the string changes slightly"},"type":"text"},{"data":{"icon":"AlertCircle","title":"Why Simple Approaches Fail","content":"Consider summing ASCII values: H('abc') = 97 + 98 + 99 = 294. This fails because 'abc' and 'bca' have the same hash (294), and 'cba' also has the same hash. Position information is lost, creating massive collisions. Any hash that ignores character positions will suffer from this fundamental flaw.","variant":"warning"},"type":"callout"},{"data":{"content":"**The Position Problem:**\n\nTwo strings are different if they have different characters OR if the same characters appear in different positions. Therefore, our hash function must encode positional information. This is where polynomials enter the picture.\n\n**The Polynomial Insight:**\n\nConsider representing a string s = s₀s₁s₂...sₙ₋₁ as a polynomial:\n\nH(s) = s₀ · bⁿ⁻¹ + s₁ · bⁿ⁻² + ... + sₙ₋₂ · b¹ + sₙ₋₁ · b⁰\n\nwhere b is called the **base** and each sᵢ is the numerical value of the character at position i.\n\nThis representation has a beautiful property: **two different strings can only have the same hash value if they are roots of the same polynomial equation**. For a random choice of b, this is extremely unlikely."},"type":"text"},{"data":{"rows":[["Sum of ASCII values","No","Very High","Yes","'abc' = 'bca' = 'cba'"],["XOR of ASCII values","No","Very High","Yes","'ab' XOR = 'ba' XOR"],["Product of ASCII values","No","High","No","'ab' × 'ba' same"],["Polynomial hash","Yes","Low (tunable)","Yes","None (probabilistic)"]],"caption":"Comparison of Hash Function Approaches","headers":["Approach","Position-Aware","Collision Rate","Rolling Update","Example Issue"]},"type":"table"}],"titleType":"number","titleNumber":1},{"id":"mathematical-foundation","title":"Mathematical Foundation of Polynomial Hashing","content":[{"data":{"content":"Let's develop the polynomial hash formula rigorously. We'll see exactly why it works and understand the mathematical machinery that makes it so effective.\n\n**The Polynomial Representation:**\n\nGiven a string s of length m, we interpret it as a polynomial evaluated at base b:\n\n$$H(s) = \\sum_{i=0}^{m-1} s[i] \\cdot b^{m-1-i} \\pmod{M}$$\n\nOr equivalently, using position from the right:\n\n$$H(s) = s[0] \\cdot b^{m-1} + s[1] \\cdot b^{m-2} + \\cdots + s[m-2] \\cdot b^1 + s[m-1] \\cdot b^0 \\pmod{M}$$\n\n**Why Polynomials?**\n\nPolynomials have a remarkable property from algebraic number theory: over a field, a polynomial of degree n-1 has at most n-1 roots. This means that for two different strings of length m, their hash values (as polynomials evaluated at base b) can only collide if b happens to be a root of their difference polynomial—which has at most m-1 roots out of M possible values of b."},"type":"text"},{"data":{"icon":"Info","title":"The Collision Probability Theorem","content":"For two distinct strings of length m, if we choose the base b uniformly at random from {0, 1, ..., M-1}, the probability that their polynomial hashes collide is at most (m-1)/M. For m = 1000 and M = 10⁹, this is less than 0.0001%!","variant":"note"},"type":"callout"},{"data":{"content":"**Concrete Example:**\n\nLet's compute the polynomial hash of \"cat\" with base b = 31 and modulus M = 10⁹ + 7:\n\n- 'c' = 99, 'a' = 97, 't' = 116 (ASCII values)\n- H(\"cat\") = 99 × 31² + 97 × 31¹ + 116 × 31⁰\n- H(\"cat\") = 99 × 961 + 97 × 31 + 116 × 1\n- H(\"cat\") = 95,139 + 3,007 + 116\n- H(\"cat\") = **98,262**\n\nNow compare with \"act\":\n\n- H(\"act\") = 97 × 31² + 99 × 31¹ + 116 × 31⁰\n- H(\"act\") = 97 × 961 + 99 × 31 + 116 × 1\n- H(\"act\") = 93,217 + 3,069 + 116\n- H(\"act\") = **96,402**\n\nDifferent strings → different hashes. The position-weighting through powers of b ensures anagrams produce different hash values."},"type":"text"},{"data":{"fileName":"polynomial_hash.py","languages":[{"code":"$63","label":"Python","value":"python"},{"code":"#include \n#include \n#include \nusing namespace std;\n\nconst long long BASE = 31;\nconst long long MOD = 1e9 + 7;\n\n/**\n * Compute the polynomial hash of a string using Horner's method.\n * \n * H(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-1] * base^0\n * \n * Time Complexity: O(n)\n * Space Complexity: O(1)\n */\nlong long polynomialHash(const string& s) {\n long long h = 0;\n for (char c : s) {\n // Horner's method for efficient polynomial evaluation\n h = (h * BASE + static_cast(c)) % MOD;\n }\n return h;\n}\n\nint main() {\n cout << \"Hash of 'cat': \" << polynomialHash(\"cat\") << endl;\n cout << \"Hash of 'act': \" << polynomialHash(\"act\") << endl;\n \n // Demonstrate that anagrams produce different hashes\n vector words = {\"hello\", \"world\", \"olleh\", \"dlrow\"};\n for (const auto& word : words) {\n cout << \"Hash of '\" << word << \"': \" << polynomialHash(word) << endl;\n }\n \n return 0;\n}","label":"C++","value":"cpp"},{"code":"/**\n * Compute the polynomial hash of a string using Horner's method.\n * \n * The hash is computed as:\n * H(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-1] * base^0\n * \n * Uses BigInt for precision with large numbers.\n * \n * Time Complexity: O(n)\n * Space Complexity: O(1)\n */\nfunction polynomialHash(\n s: string, \n base: bigint = 31n, \n mod: bigint = BigInt(1e9 + 7)\n): bigint {\n let h = 0n;\n for (const char of s) {\n // Horner's method: multiply previous by base, add new character\n h = (h * base + BigInt(char.charCodeAt(0))) % mod;\n }\n return h;\n}\n\n// Example usage\nconsole.log(`Hash of 'cat': ${polynomialHash('cat')}`);\nconsole.log(`Hash of 'act': ${polynomialHash('act')}`);\n\n// Demonstrate collision resistance with anagrams\nconst words = ['hello', 'world', 'olleh', 'dlrow', 'cat', 'tac'];\nfor (const word of words) {\n console.log(` '${word}' -> ${polynomialHash(word)}`);\n}","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"icon":"Lightbulb","title":"Horner's Method — The Efficiency Secret","content":"Instead of computing each power of base separately (which would require O(n²) operations or O(n) with precomputation), we use Horner's method to evaluate the polynomial iteratively. This transforms H(s) = s₀b³ + s₁b² + s₂b + s₃ into H(s) = ((s₀ × b + s₁) × b + s₂) × b + s₃, computing the entire hash in a single O(n) pass with O(1) space.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"rolling-hash-technique","title":"The Rolling Hash Technique","content":[{"data":{"content":"The true power of polynomial hashing emerges when we need to compute hashes for **many overlapping substrings**. In pattern matching, we slide a window of length m across a text of length n, computing the hash of each window position. A naive approach would compute n-m+1 hashes, each in O(m) time, for O((n-m) × m) total time.\n\n**The Rolling Hash Insight:**\n\nConsider two adjacent windows in the text:\n\n- Window at position i: text[i..i+m-1]\n- Window at position i+1: text[i+1..i+m]\n\nThese windows share m-1 characters! The rolling hash exploits this overlap to compute the new hash from the old hash in O(1) time.\n\n**The Rolling Update Formula:**\n\nLet H(i) = hash of text[i..i+m-1].\n\nThen:\n\n$$H(i+1) = (H(i) - text[i] \\cdot b^{m-1}) \\cdot b + text[i+m] \\pmod{M}$$\n\n**Intuition:**\n1. **Subtract** the contribution of the leftmost character (scaled by b^(m-1))\n2. **Multiply** by b (shift all remaining characters one position left in the polynomial)\n3. **Add** the new rightmost character (at position b⁰)"},"type":"text"},{"data":{"left":[{"data":{"items":["Compute each window hash from scratch","O(m) time per window position","O((n-m) × m) total time","For n=10⁶, m=1000: ~10⁹ operations","Dominant factor in naive pattern matching"],"title":{"icon":"XCircle","text":"Without Rolling Hash","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Compute first window hash in O(m)","Update each subsequent window in O(1)","O(n) total time for all windows","For n=10⁶, m=1000: ~10⁶ operations","1000× speedup in this example!"],"title":{"icon":"CheckCircle","text":"With Rolling Hash","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"content":"**Step-by-Step Example:**\n\nLet's trace through rolling the hash for text \"abcde\" with window size 3, using base=31:\n\n**Initial Hash (window \"abc\"):**\n- H₀ = 97×31² + 98×31¹ + 99×31⁰ = 93,217 + 3,038 + 99 = 96,354\n\n**Roll to \"bcd\" (remove 'a'=97, add 'd'=100):**\n- H₁ = (H₀ - 97×31²) × 31 + 100\n- H₁ = (96,354 - 93,217) × 31 + 100\n- H₁ = 3,137 × 31 + 100 = 97,247 + 100 = 97,347\n\n**Verification (compute directly):**\n- H(\"bcd\") = 98×31² + 99×31¹ + 100×31⁰ = 94,178 + 3,069 + 100 = 97,347 ✓\n\n**Roll to \"cde\" (remove 'b'=98, add 'e'=101):**\n- H₂ = (H₁ - 98×31²) × 31 + 101\n- H₂ = (97,347 - 94,178) × 31 + 101\n- H₂ = 3,169 × 31 + 101 = 98,239 + 101 = 98,340\n\n**Verification:**\n- H(\"cde\") = 99×31² + 100×31¹ + 101×31⁰ = 95,139 + 3,100 + 101 = 98,340 ✓"},"type":"text"},{"data":{"fileName":"rolling_hash.py","languages":[{"code":"$64","label":"Python","value":"python"}]},"type":"code"}],"titleType":"number","titleNumber":3},{"id":"prefix-hash-arrays","title":"Precomputing Hash Prefix Arrays","content":[{"data":{"content":"For many applications, we need to query the hash of arbitrary substrings, not just consecutive windows. The **prefix hash array** technique enables O(1) substring hash queries after O(n) preprocessing.\n\n**The Prefix Hash Concept:**\n\nDefine prefix_hash[i] = H(s[0..i-1]) = hash of the first i characters.\n\nThen for any substring s[l..r] (0-indexed, inclusive):\n\n$$H(s[l..r]) = \\frac{prefix\\_hash[r+1] - prefix\\_hash[l] \\cdot b^{r-l+1}}{1} \\pmod{M}$$\n\nOr more precisely:\n\n$$H(s[l..r]) = (prefix\\_hash[r+1] - prefix\\_hash[l] \\cdot power[r-l+1]) \\mod M$$\n\nwhere power[k] = b^k mod M."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Intuition: Place Value Analogy","content":"Think of it like extracting digits from a decimal number. If you have 12345 and want digits 2-4 (\"234\"), you subtract 12000 and divide by 10. Similarly, prefix_hash[5] contains s[0..4], and to get s[2..4], we subtract the contribution of s[0..1] (properly scaled) from prefix_hash[5] and adjust the powers.","variant":"tip"},"type":"callout"},{"data":{"content":"**Why This Works:**\n\nLet's trace through mathematically:\n\n```\nprefix_hash[5] = s[0]·b⁴ + s[1]·b³ + s[2]·b² + s[3]·b¹ + s[4]·b⁰\nprefix_hash[2] = s[0]·b¹ + s[1]·b⁰\n\nprefix_hash[2] × b³ = s[0]·b⁴ + s[1]·b³ (scaled to match)\n\nprefix_hash[5] - prefix_hash[2] × b³ = s[2]·b² + s[3]·b¹ + s[4]·b⁰ = H(s[2..4])\n```\n\nThe key insight is that we multiply the prefix hash by an appropriate power of b to align the polynomial terms before subtraction.\n\n**Implementation Considerations:**\n\n1. **Precompute powers**: Store power[i] = b^i mod M for i = 0 to n\n2. **Handle negative modulo**: (a - b) mod M can be negative in some languages\n3. **1-indexed convenience**: Use prefix_hash[0] = 0 for easier formula"},"type":"text"},{"data":{"fileName":"prefix_hash_array.py","languages":[{"code":"$65","label":"Python","value":"python"}]},"type":"code"}],"titleType":"number","titleNumber":4},{"id":"polynomial-distribution","title":"Why Polynomials Give Good Distribution","content":[{"data":{"content":"It's worth understanding *why* polynomial hashing works so well from a theoretical perspective. The collision resistance of polynomial hashing comes from deep results in algebra and number theory.\n\n**The Schwartz-Zippel Lemma:**\n\nThis fundamental result states: For a non-zero polynomial P(x) of degree d over a field F, if we pick x uniformly at random from a finite subset S ⊆ F, then:\n\nPr[P(x) = 0] ≤ d / |S|\n\n**Application to String Hashing:**\n\nGiven two distinct strings s₁ and s₂ of length m, define:\n\nP(x) = H(s₁, x) - H(s₂, x)\n\nwhere H(s, x) is the polynomial hash of s with base x.\n\nSince s₁ ≠ s₂, at least one coefficient differs, so P(x) is a non-zero polynomial of degree at most m-1.\n\nBy Schwartz-Zippel: Pr[P(b) = 0] ≤ (m-1)/M\n\nFor m = 10³ and M = 10⁹: collision probability < 10⁻⁶ per pair!"},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Birthday Paradox Warning","content":"The above analysis is for a single pair of strings. When comparing many strings (like all substrings of length m), the birthday paradox kicks in. With √M ≈ 31,623 substrings, you have a ~50% chance of at least one collision. This is why using a large modulus (10⁹+7) or multiple hash functions is crucial for large-scale applications.","variant":"note"},"type":"callout"},{"data":{"content":"**Uniformity of Distribution:**\n\nPolynomial hashes distribute uniformly because:\n\n1. **Independence of coefficients**: Each character contributes independently to the final hash value\n2. **Power weighting**: Different positions have different weights (b^i), preventing collision patterns\n3. **Field properties**: When M is prime, arithmetic mod M behaves like a mathematical field, maximizing randomness\n\n**Why Prime Moduli Matter:**\n\nConsider what happens with a composite modulus like M = 256 (2⁸):\n- If b is even, b² is divisible by 4, b³ by 8, b⁴ by 16...\n- After just 8 terms, b⁸ ≡ 0 (mod 256)\n- Early characters stop contributing to the hash!\n\nWith a prime M:\n- No non-trivial factors exist\n- Powers of b cycle through many distinct values\n- Every character contributes meaningfully"},"type":"text"},{"data":{"rows":[["Single pair (m=1000)","~0.1%","~0.0001%","~10⁻¹³%"],["100 substrings","~10%","~0.01%","~10⁻⁹%"],["10,000 substrings","~99.995%","~0.5%","~10⁻⁵%"],["1,000,000 substrings","Certain","~39%","~0.005%"]],"caption":"Collision Probability Analysis","headers":["Scenario","M = 10⁶","M = 10⁹","M = 10¹⁸ (double hash)"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"Practical Recommendation","content":"For competitive programming and most applications: Use M = 10⁹ + 7 (this is prime). For production systems handling large data: Use double hashing (two different base/mod pairs) or a 64-bit hash. For cryptographic applications: Polynomial hashes are NOT secure—use SHA-256 or similar.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"summary-connections","title":"Summary and Connections","content":[{"data":{"content":"We've now established the mathematical foundations of polynomial rolling hashes—the workhorse technique for efficient string matching. Let's consolidate the key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**Polynomial representation encodes position**: Each character's contribution is weighted by a power of the base, ensuring anagrams produce different hashes.","**Rolling updates in O(1)**: The key formula H(i+1) = (H(i) - old × b^(m-1)) × b + new allows sliding window hash computation in constant time per step.","**Prefix arrays enable O(1) substring queries**: After O(n) preprocessing, any substring hash can be computed in constant time.","**Collision probability is mathematically bounded**: By Schwartz-Zippel, random collisions are extremely rare with proper parameters.","**Horner's method provides efficiency**: We can evaluate the polynomial in O(n) time and O(1) space using iterative accumulation.","**Prime moduli maximize distribution quality**: Using a prime modulus ensures all powers of the base remain distinct and contribute meaningfully."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Connections to Other Topics:**\n\n- **Rabin-Karp algorithm**: Uses rolling hash as its core—now you understand exactly how it achieves O(n+m) average time\n- **Longest common substring**: Prefix hash arrays + binary search gives O(n log n) solution\n- **Suffix arrays**: Can be constructed using hashing + sorting\n- **Palindrome detection**: Compare H(s[i..j]) with H(reverse(s[i..j]))\n\n**What's Next:**\n\nNow that we understand polynomial hashing, the next critical question is: How do we choose the base and modulus? Poor choices can lead to more collisions, vulnerability to adversarial inputs, or arithmetic overflow. The next page covers parameter selection in depth."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand polynomial rolling hashes from first principles—the mathematical foundation, the rolling update technique, prefix array preprocessing, and the theoretical guarantees. These concepts form the basis for all string hashing applications we'll explore in subsequent pages.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":6}],"isLocked":false},{"id":"seed_0f2206959dfdbe9255d4111bd589fd9c","title":"Choosing Hash Base and Modulus","order":1,"content":null,"isLocked":true},{"id":"seed_40f030748a4ba9cd3a22562b65978c94","title":"Handling Collisions with Multiple Hashes","order":2,"content":null,"isLocked":true},{"id":"seed_f0378b95cf85889e09c2b9346336bb51","title":"Applications Beyond Exact Matching","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792303949478,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"string-hashing-techniques"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"string-hashing-techniques\"},\"type\":\"query\"}]"},{"dehydratedAt":1792303949480,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792303949477,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_aeccde5fccc78bf3a22adc4cb4ee0e03"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_aeccde5fccc78bf3a22adc4cb4ee0e03\"},\"type\":\"query\"}]"},{"dehydratedAt":1792303949480,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792303949477,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_0f2206959dfdbe9255d4111bd589fd9c"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_0f2206959dfdbe9255d4111bd589fd9c\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792303949480,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792303949477,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_0f2206959dfdbe9255d4111bd589fd9c"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_0f2206959dfdbe9255d4111bd589fd9c\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792303949480,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792303949477,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_0f2206959dfdbe9255d4111bd589fd9c"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_0f2206959dfdbe9255d4111bd589fd9c\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792303949480,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_0f2206959dfdbe9255d4111bd589fd9c","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_0f2206959dfdbe9255d4111bd589fd9c\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@66"}]},"children":"$L67"}]