Problem link ও উৎস
- **Original source:** CP-Algorithms — String Hashing
- **Platform:** CP-Algorithms —
- **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 কাঠামো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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 ছোট থাকে।
### Input ও output {#6-example-input-and-output}
```text
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 মিললে একবার সরাসরি `==` করা ভালো।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো প্রতিটা মানুষের **আঙুলের ছাপ**। পুরো মানুষটাকে তুলনা না করে, শুধু ছোট্ট ছাপ মিলিয়ে চট করে বলা যায় "এ কি সেই লোক?"। ছাপ ছোট, মেলানো দ্রুত — যদিও খুব ক্বচিৎ দুজনের ছাপ কাছাকাছি হতে পারে (collision)।
string hash তেমন: পুরো লম্বা string character-by-character না মিলিয়ে, তাদের ছোট্ট fingerprint (একটা সংখ্যা) মিলিয়ে দ্রুত আঁচ করা। ছাপ যত ভালো বানানো (বড় prime M, ভালো base B), দুজনের ছাপ ভুলক্রমে মেলার সম্ভাবনা তত কম। সম্পূর্ণ নিশ্চিত হতে অবশ্য একবার পুরো মিলিয়ে নিতে হয় — ঠিক যেমন ছাপ মিললে তবেই গভীর পরীক্ষা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 করা।
### ভেতরের অঙ্ক {#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-সংখ্যার চেয়ে বড় নিলে ভালো ছড়ায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
hash ছাড়া "দুটো string সমান?" — সরাসরি character-by-character তুলনা। আর "একটা string আরেকটার মধ্যে আছে?" (substring search) — প্রতিটা position-এ পুরো pattern মেলানো:
```python
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
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):
```python
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 ইঙ্গিত, প্রমাণ নয়।
### ছবিতে বোঝা {#5-visual-explanation}
`"abc"`-এর hash, B = 31, M = একটা prime (ছোট করে M = 1009 ধরি):
```text
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-এর সাথে পাশাপাশি দেখো:
```text
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)
```
### ছোট input-এ ধাপে ধাপে {#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 এটাই যাচাই করছে)।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
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)`।
```text
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-এর উত্তর এর সাথে মিলবে।
```text
for s in [...]:
assert poly_hash(s) == poly_hash_naive(s)
```
এই loop Horner আর naive — দুই পথে একই hash কিনা মিলিয়ে দেখছে। এটাই নিশ্চিত করে আমাদের "প্রতি step-এ mod" সঠিক (028-এর নিয়ম কাজ করছে)। order-sensitivity আর duplicate detection-ও যাচাই করা। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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++-এ সাবধান।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **Rabin-Karp substring search** (LeetCode — Implement strStr(),