038 — Hashing with Mod¶

Level 2-এর শেষ problem — আর শেষটা সবচেয়ে মজার: mod-এর একটা বাস্তব application। একটা পুরো string-কে একটামাত্র সংখ্যায় (fingerprint-এ) নামিয়ে দুটো string সমান কিনা চটজলদি আঁচ করা — এটাই polynomial string hashing। আর মজার ব্যাপার: এর কাঠামো হুবহু 031-এর big number mod, শুধু base 10-এর জায়গায় 31।

Source¶

Original source: CP-Algorithms — String Hashing
Platform: CP-Algorithms — https://cp-algorithms.com/string/string-hashing.html
Topic: Math-based programming fundamentals → Level 2: Modular Arithmetic
Difficulty: Medium
Pattern: polynomial hash
Basic idea inherited from: 028 — Modular Multiplication; সঙ্গে 031-এর digit-by-digit কাঠামো

1. Problem in simple words¶

একটা string s দেওয়া। বানাতে হবে তার একটা hash — একটা সংখ্যা (fingerprint), যাতে:

একই string সবসময় একই hash দেয়,
দুটো ভিন্ন string সাধারণত ভিন্ন hash দেয় (কালেভদ্রে মিলে যেতে পারে — collision),
দুটো string সমান কিনা hash মিলিয়ে O(1)-এ আঁচ করা যায়।

মূল কৌশল: string-টাকে একটা base-B সংখ্যা ভাবো, আর সেই সংখ্যাকে একটা বড় prime M দিয়ে mod নাও যাতে hash ছোট থাকে।

2. What is the math idea?¶

মূল idea — polynomial hashing। string s = s₀ s₁ s₂ ... s_{n−1}-কে base-B-তে একটা সংখ্যা ধরো:

hash(s) = (s₀·B^{n−1} + s₁·B^{n−2} + ... + s_{n−1}·B⁰) mod M

এটা গণনা করার সবচেয়ে সাফ উপায় Horner's method (031-এর মতো):

h = (h × B + ord(ch)) mod M, প্রতি character-এ

প্রতি step-এ × B মানে আগের সবাইকে এক "ঘর" উপরে তোলা, তারপর নতুন character যোগ — আর সঙ্গে সঙ্গে % M (028-এর modular multiplication + addition)। M বড় prime নিলে collision বিরল; B character-সংখ্যার চেয়ে বড় নিলে ভালো ছড়ায়।

3. Which basic idea does this inherit from?¶

দুটো শিকড়:

028 — Modular Multiplication (+ 027 addition): প্রতি step-এ h × B + ord(ch)-এ গুণ আর যোগ — দুটোতেই % M। এই "প্রতি step-এ mod" না থাকলে hash অসীম বড় হতো।
031 — Large Number Mod: হুবহু সেই r = (r*10 + digit) % m কাঠামো! শুধু base 10 → B, আর digit → ord(ch)। concept-notes-এ স্পষ্ট বলা — big_mod আর poly_hash একই হাড়ের গঠন।

মানে hashing নতুন জাদু নয় — চেনা digit-by-digit mod-কে character-by-character বানিয়ে fingerprint করা।

4. Real-life analogy¶

ভাবো প্রতিটা মানুষের আঙুলের ছাপ। পুরো মানুষটাকে তুলনা না করে, শুধু ছোট্ট ছাপ মিলিয়ে চট করে বলা যায় "এ কি সেই লোক?"। ছাপ ছোট, মেলানো দ্রুত — যদিও খুব ক্বচিৎ দুজনের ছাপ কাছাকাছি হতে পারে (collision)।

string hash তেমন: পুরো লম্বা string character-by-character না মিলিয়ে, তাদের ছোট্ট fingerprint (একটা সংখ্যা) মিলিয়ে দ্রুত আঁচ করা। ছাপ যত ভালো বানানো (বড় prime M, ভালো base B), দুজনের ছাপ ভুলক্রমে মেলার সম্ভাবনা তত কম। সম্পূর্ণ নিশ্চিত হতে অবশ্য একবার পুরো মিলিয়ে নিতে হয় — ঠিক যেমন ছাপ মিললে তবেই গভীর পরীক্ষা।

5. Visual explanation¶

"abc"-এর hash, B = 31, M = একটা prime (ছোট করে M = 1009 ধরি):

ord('a')=97, ord('b')=98, ord('c')=99

Horner ধরে (h শুরুতে 0):
'a': h = (0 × 31 + 97) % 1009 = 97
'b': h = (97 × 31 + 98) % 1009 = 3105 % 1009 = 78
'c': h = (78 × 31 + 99) % 1009 = 2517 % 1009 = 499

hash("abc") = 499   <- পুরো string একটা সংখ্যায় নামল

কাঠামোটা 031-এর সাথে পাশাপাশি দেখো:

031 big_mod:   r = (r * 10 + digit)   % m      <- base 10, digit
038 poly_hash: h = (h * B  + ord(ch)) % M      <- base B, character
               ^^^^^^^^^^^^^^^^^^^^^^^ একই হাড়! শুধু 10->B, digit->ord(ch)

6. Example input and output¶

s        ->  hash (B=31, M=10^9+7)     লক্ষ্য
-------------------------------------------------------
""       ->  0                         খালি string
"a"      ->  97                        ord('a')
"abc"    ->  নির্দিষ্ট একটা সংখ্যা       deterministic
"abc"    ->  hash("abc") আবার একই      একই string -> একই hash

তুলনা:
hash("abc") == hash("abc")  ->  True   (একই)
hash("abc") == hash("abd")  ->  False  (ভিন্ন, সাধারণত)
hash("listen") vs hash("silent")  ->  ভিন্ন (anagram-ও আলাদা, কারণ ক্রম গোনে)

মূল ধর্ম: deterministic (একই input → একই output) আর order-sensitive ("abc" ≠ "cba")। collision বিরল কিন্তু সম্ভব — তাই সমতা নিশ্চিত করতে hash মিললে একবার সরাসরি == করা ভালো।

7. Brute force thinking¶

hash ছাড়া "দুটো string সমান?" — সরাসরি character-by-character তুলনা। আর "একটা string আরেকটার মধ্যে আছে?" (substring search) — প্রতিটা position-এ পুরো pattern মেলানো:

def equal_brute(a, b):
    return a == b               # Python-এ ভেতরে character-by-character

def count_occurrences_brute(text, pat):
    n, m = len(text), len(pat)
    count = 0
    for i in range(n - m + 1):
        if text[i:i+m] == pat:  # প্রতি position-এ পুরো pat মেলাও
            count += 1
    return count

সঠিক, কিন্তু প্রতিবার পুরো string/pattern মেলানো — সেখানেই hashing-এর সুবিধা।

8. Why brute force may be slow¶

একবার দুটো string মেলানো O(length)। কিন্তু অনেকবার মেলাতে হলে (যেমন substring search, বা বহু string-এর মধ্যে duplicate খোঁজা) খরচ জমে যায়:

text length n, pattern length m, naive substring search:
  প্রতি position-এ O(m) তুলনা, n position  ->  O(n × m)
  hash দিয়ে (rolling): প্রতি position O(1) তুলনা ->  O(n + m)

বহু string duplicate খোঁজা: জোড়ায় জোড়ায় তুলনা O(k² × len)
  hash দিয়ে: প্রতিটার hash O(len), তারপর set-এ O(1)  ->  O(k × len)

মূল শিক্ষা: পুরো string বারবার না মিলিয়ে, একবার fingerprint বানিয়ে সেই ছোট সংখ্যা মেলাও।

9. Better thinking¶

polynomial hash — Horner + প্রতি step-এ mod (031-এর কাঠামো, base B):

def poly_hash(s, B=31, M=10**9 + 7):
    h = 0
    for ch in s:
        h = (h * B + ord(ch)) % M
    return h

দুটো string সমান কিনা আঁচ: hash মেলাও (মিললে নিশ্চিত হতে একবার ==)। duplicate খুঁজতে: সব hash একটা set-এ রাখো। প্রতিটা hash O(len)-এ, তারপর তুলনা O(1)।

collision আরও কমাতে চাইলে double hashing (দুটো ভিন্ন (B, M) জোড়া) ব্যবহার হয় — দুটোই মিললে তবেই সমান ধরা, ভুলের সম্ভাবনা নগণ্য।

10. Thinking tweak¶

আসল "আহা!": একটা পুরো string-কে base-B সংখ্যা ভেবে mod নাও — পেয়ে গেলে একটা ছোট fingerprint, যা দিয়ে সমতা O(1)-এ আঁচ করা যায়। আর এটা 031-এর big number mod-এরই রূপ — শুধু base 10 → B, digit → character।

দুটো design-tweak মনে রাখো:

M বড় prime (যেমন 10⁹+7): ছোট/composite M-এ collision বেশি; বড় prime-এ বিরল।
B character-সংখ্যার চেয়ে বড় (lowercase-এ 31/53): ভালো ছড়ায়, কম collision। আর hash মিললেও নিশ্চিত হতে একবার সরাসরি মিলিয়ে নাও — fingerprint ইঙ্গিত, প্রমাণ নয়।

11. Step-by-step dry run¶

poly_hash("abc", B=31, M=1009) (ছোট M দিয়ে দেখি):

step	ch	ord(ch)	h (আগে)	h*31 + ord	% 1009
শুরু	—	—	0	—	0
1	'a'	97	0	0×31 + 97 = 97	97
2	'b'	98	97	97×31 + 98 = 3105	3105 % 1009 = 78
3	'c'	99	78	78×31 + 99 = 2517	2517 % 1009 = 499

hash("abc") = 499 (M=1009-এ)। লক্ষ করো h কখনো M-এর ধারেকাছের বেশি বড় হয়নি — সংখ্যা ছোট থাকল, যদিও string-কে base-31 সংখ্যা ভাবলে বিশাল হতো।

Check (naive পথে): "abc"-এর পুরো base-31 মান = 97×31² + 98×31 + 99 = 97×961 + 3038 + 99 = 93217 + 3137 = 96354। আর 96354 % 1009 = 499 — Horner-এর উত্তরের সাথে মিলল! এটাই concept-notes-এর শিক্ষা: প্রতি step-এ mod নিলেও শেষ উত্তর একই (028-এর নিয়ম)। হাতে করলে সবসময় Python-এর সাথে মিলিয়ে নাও; mismatch পেলে হাতের হিসাবেই ফাঁক ধরে নিয়ে আবার করো (নিচের assert এটাই যাচাই করছে)।

12. Python solution¶

def poly_hash(s, B=31, M=10**9 + 7):
    """string s-এর polynomial hash (Horner + প্রতি step mod)। 031-এর কাঠামো।"""
    h = 0
    for ch in s:
        h = (h * B + ord(ch)) % M
    return h


def poly_hash_naive(s, B=31, M=10**9 + 7):
    """যাচাইয়ের জন্য: আগে পুরো base-B সংখ্যা, তারপর একবার mod।"""
    n = len(s)
    total = 0
    for i, ch in enumerate(s):
        total += ord(ch) * (B ** (n - 1 - i))
    return total % M


def first_duplicate_hash(strings, B=31, M=10**9 + 7):
    """hash দিয়ে duplicate string আছে কিনা (collision বিরল ধরে)।"""
    seen = set()
    for s in strings:
        hs = poly_hash(s, B, M)
        if hs in seen:
            return True
        seen.add(hs)
    return False


# --- মূল ধর্ম: deterministic ও naive-এর সাথে মিল ---
assert poly_hash("") == 0
assert poly_hash("a") == 97                      # ord('a')
assert poly_hash("abc") == poly_hash("abc")      # একই string -> একই hash

# Horner আর naive (পুরো সংখ্যা তারপর mod) এক উত্তর দেওয়া উচিত:
for s in ["", "a", "ab", "abc", "hello", "listen", "silent", "aaaa", "zzz"]:
    assert poly_hash(s) == poly_hash_naive(s)

# order-sensitive: ভিন্ন ক্রম সাধারণত ভিন্ন hash
assert poly_hash("abc") != poly_hash("cba")
assert poly_hash("listen") != poly_hash("silent")

# ছোট M দিয়ে dry run মিলিয়ে দেখা (হাতের হিসাব নয়, Python সত্য):
assert poly_hash("abc", 31, 1009) == poly_hash_naive("abc", 31, 1009)

# duplicate detection:
assert first_duplicate_hash(["cat", "dog", "cat"]) is True
assert first_duplicate_hash(["cat", "dog", "bird"]) is False

print(poly_hash("a"))                            # 97
print(poly_hash("abc"))                          # একটা নির্দিষ্ট বড় সংখ্যা
print(poly_hash("abc", 31, 1009))                # ছোট M-এ মান
print("সব test pass!")

13. Line-by-line explanation¶

    h = 0
    for ch in s:
        h = (h * B + ord(ch)) % M
    return h

h শুরু 0। প্রতিটা character-এ: h * B মানে আগের সবাইকে এক ঘর উপরে তোলা (base-B-তে শিফট), + ord(ch) নতুন character যোগ, তারপর % M। এটাই Horner — হুবহু 031-এর r*10 + digit, base 10-এর জায়গায় B, digit-এর জায়গায় ord(ch)।

def poly_hash_naive(s, B=31, M=...):
    total = 0
    for i, ch in enumerate(s):
        total += ord(ch) * (B ** (n - 1 - i))
    return total % M

সংজ্ঞা সরাসরি: প্রতিটা character-এর place value B^(n−1−i) গুণ, সব যোগ, শেষে একবার mod। এটা ধীর/বড় (পুরো সংখ্যা বানায়) — শুধু যাচাইয়ের জন্য, Horner-এর উত্তর এর সাথে মিলবে।

for s in [...]:
    assert poly_hash(s) == poly_hash_naive(s)

এই loop Horner আর naive — দুই পথে একই hash কিনা মিলিয়ে দেখছে। এটাই নিশ্চিত করে আমাদের "প্রতি step-এ mod" সঠিক (028-এর নিয়ম কাজ করছে)। order-sensitivity আর duplicate detection-ও যাচাই করা। সব ঠিক থাকলে শেষে সব test pass!।

14. Output walkthrough¶

চালালে যা ছাপবে:

97
96354
499
সব test pass!

প্রথম লাইন poly_hash("a") → 97 (ord('a'))। দ্বিতীয় poly_hash("abc") mod 10⁹+7 → 96354 (যেহেতু base-31 মান 96354 নিজেই 10⁹+7-এর চেয়ে ছোট, mod-এ অপরিবর্তিত)। তৃতীয় poly_hash("abc", 31, 1009) → 499 (ছোট M-এ, dry run-এর সাথে মেলে — Python-এ যাচাই করা)। আগের সব assert (naive-এর সাথে মিল সহ) চুপচাপ pass — তারপর সব test pass!।

15. Time complexity¶

O(n) একটা string hash করতে (n = length); প্রতিটা character-এ O(1) কাজ (গুণ, যোগ, mod)। তুলনা hash মিলিয়ে O(1)। substring search-এ rolling hash দিয়ে O(n + m), naive O(n×m)-এর জায়গায়। naive_hash O(n) কিন্তু বড় সংখ্যার power বানায় বলে constant factor ভারী।

16. Space complexity¶

O(1) একটা hash-এর জন্য (শুধু h)। duplicate detection-এ সব hash রাখতে O(k) (k = string সংখ্যা)। Horner পুরো big number বানায় না, তাই naive-এর তুলনায় সাশ্রয়ী।

17. Common mistakes¶

ছোট বা composite M বাছা — collision বেড়ে যায়; বড় prime (10⁹+7 বা 998244353) নাও।
B খুব ছোট (যেমন 1 বা 2) — ভালো ছড়ায় না; B character-সংখ্যার চেয়ে বড় (lowercase-এ 31/53) নাও।
প্রতি step-এ mod না নেওয়া — তাহলে h অসীম বড় (031-এর সমস্যাই ফিরে আসে); C++-এ overflow।
hash মিললেই "সমান" ধরে নেওয়া — collision সম্ভব; নিশ্চিত হতে hash মিললে একবার সরাসরি == করো (বা double hashing)।
character-কে সরাসরি ব্যবহার — ord(ch) দিয়ে সংখ্যায় আনো; নাহলে গুণ/যোগ চলবে না।
ord 0 দেওয়া বা empty-কে অবহেলা — কিছু scheme-এ ord-এ +1 যোগ করা হয় যাতে 'a'=1 ইত্যাদি; নাহলে leading character-এর তথ্য চাপা পড়তে পারে (advanced; basic-এ ord সরাসরি ঠিক)।
negative % (C++) — Python-এ non-negative; C++-এ সাবধান।

18. Harder problems that inherit this idea¶

Rabin-Karp substring search (LeetCode — Implement strStr(), https://leetcode.com/problems/implement-strstr/) — rolling hash দিয়ে O(n + m) pattern matching; এই poly_hash-এর সরাসরি সম্প্রসারণ।
LeetCode — Longest Duplicate Substring (https://leetcode.com/problems/longest-duplicate-substring/) — binary search + rolling hash; hashing-এর শক্তিশালী প্রয়োগ।
CP-Algorithms String Hashing page-এর substring hash, distinct substrings গোনা — prefix hash + power precompute।

19. Pattern learned¶

Polynomial string hashing — string-কে base-B সংখ্যা ভেবে h = (h*B + ord(ch)) % M (বড় prime M, ভালো base B)। 031-এর digit-by-digit mod-এর রূপ। fingerprint দিয়ে সমতা O(1)-এ আঁচ; collision বিরল, তাই মিললে নিশ্চিত হতে একবার মিলিয়ে নাও।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "string hash = h = (h*B + ord(ch)) % M — 031-এর big-number-mod, base 10→B। বড় prime M, base B; fingerprint মেলাও O(1)-এ, কিন্তু collision-এর জন্য মিললে একবার সরাসরি যাচাই। 'string সমতা/substring বারবার মেলাতে হবে' দেখলেই hashing।"

এটাই Level 2-এর শেষ problem! → পুরো level-এর map দেখতে ../README.md-এ ফেরো, checklist মেলাও, তারপর Level 3: Counting & Combinatorics-এ যেখানে এখানকার nCr mod p রাজা হয়ে ফিরবে। সম্পর্কিত → 031 — Large Number Mod, 028 — Modular Multiplication।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "common interview pattern" / "CP-তে নিত্য দরকারি" লেখা।