কনটেন্টে যান

022 — CSES String Matching (Rolling Hash)

Problem link ও উৎস

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

Text S ও pattern P দেওয়া; overlap সহ P কতবার S-এ আসে তা গুনতে হবে। এটি নির্দিষ্ট CSES task। আগের অস্পষ্ট Codeforces placeholder বাদ দেওয়া হয়েছে; পুরনো link সচল রাখতে filename রাখা হয়েছে। নিচের rolling hash শেখার জন্য; repeated match-এ worst case ধীর। শেষে exact linear KMP সমাধান আছে।

উদাহরণ
S = "abababab", P = "ab"
"ab" আসে index 0, 2, 4, 6-এ
উত্তর: 4

Input ও output

উদাহরণ
Input : S = "abababab", P = "ab"     Output: 4   (index 0,2,4,6)
Input : S = "aaaaa",    P = "aa"     Output: 4   (index 0,1,2,3; overlap সহ)
Input : S = "abcdef",   P = "xyz"    Output: 0
Input : S = "mississippi", P = "issi" Output: 2  (index 1, 4)
Input : S = "hello",    P = ""       Output: 0   (খালি pattern গোনা হয় না)

চেনা উদাহরণে বোঝা

ভাবো একটা লম্বা সংখ্যা-ফিতের উপর জানালা সরাচ্ছ আর প্রতিবার জানালার ভেতরের অঙ্কগুলোকে একটা একক সংখ্যা হিসেবে পড়ছ। জানালা এক ঘর ডানে সরালে তুমি পুরোটা আবার পড়ো না — বাঁয়ের সবচেয়ে বড় স্থানীয় মানের অঙ্কটা বাদ দাও, বাকিটা ১০ গুণ করো (সব এক ঘর বাঁয়ে সরল), ডানে নতুন অঙ্ক বসাও। ঠিক এভাবেই rolling hash এক ঘর সরায় — পুরো পুনর্গণনা ছাড়াই নতুন "সংখ্যা" পেয়ে যায়।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা Pattern 7 (rolling hash)-এর পূর্ণ রূপ — Repeated DNA Sequences (#19)-এ যে window-কে key ভাবার teaser দেখেছ, তার বড় সংস্করণ। মূল ধারণা place-value/positional সংখ্যা: string-কে কোনো base-এর একটা সংখ্যা ভাবা, যা ../../01-math-based-programming-fundamentals/02-modular-arithmetic/-এর modular arithmetic-এর উপর দাঁড়ানো। পুরো treatment CP-Algorithms-এ: https://cp-algorithms.com/string/string-hashing.html।

ভেতরের যুক্তি

লুকানো গণিত হলো polynomial hashing: দৈর্ঘ্য-m একটা string c0 c1 ... c(m-1)-কে ধরা হয় সংখ্যা c0·base^(m-1) + c1·base^(m-2) + ... + c(m-1) (সব mod একটা বড় prime)। মূল সৌন্দর্য — window এক ঘর ডানে সরালে এই সংখ্যা শূন্য থেকে বের করতে হয় না: বেরিয়ে-যাওয়া অক্ষরের contribution = c·base^(m-1) বিয়োগ করো, বাকিটা base দিয়ে গুণো (সবাই এক ঘর বাঁয়ে সরল), নতুন অক্ষর যোগ করো। তাই প্রতিটা slide O(1)।

কী দিয়ে তথ্য রাখব

মূলত কয়েকটা integer (running hash, pattern hash, base^(m-1)) আর modular arithmetic — কোনো ভারী structure লাগে না। তবে "কোন কোন window pattern-এর সমান" বা "distinct substring কতগুলো" জাতীয় variant-এ একটা hash set / Counter লাগে দেখা hash জমাতে — সেখানেই hashing chapter-এর seen-set ফিরে আসে।

এটি কেন উপযুক্ত

দৈর্ঘ্য m-এর string তুলনা O(m); fixed-size hash তুলনা O(1)। Rolling update-এ সব window-এর hash তৈরি O(n+m), কিন্তু hash মিললে আসল substring যাচাইয়ের খরচও যোগ করতে হবে। তাই নিচের verified rolling-hash code-এর worst case O(nm)।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: text-এর প্রতিটা শুরু-position-এ pattern-টা অক্ষরে অক্ষরে মিলিয়ে দেখো।

উদাহরণ
count = 0
প্রতিটা শুরু i (0 .. n-m)-র জন্য:
    S[i : i+m] == P হলে count += 1
return count

কোথায় বেশি কাজ হচ্ছে

প্রতিটা শুরু-position-এ সবচেয়ে খারাপ ক্ষেত্রে mটা অক্ষর মেলাতে হয় — মোট O(n·m)। n ও m দুটোই বড় হলে (CF-তে 10^5–10^6) এটা time limit ছাড়ায়। অপচয়টা: পাশাপাশি দুটো window-এর প্রায় সব অক্ষর একই, তবু আমরা প্রতিবার গোড়া থেকে তুলনা করছি। hash তুলনা সেই কাজটাকে O(1)-এ নামায় (rolling-এ window-এর hash-ও O(1) আপডেট)।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: দুটো string সমান কি না, তা (প্রায় নিশ্চিতভাবে) তাদের একটামাত্র সংখ্যা — hash — তুলনা করে বলা যায়, পুরো অক্ষর না মিলিয়ে। আর সেই hash window slide-এ O(1)-এ আপডেট হয়। দুর্লভ collision সামলাতে hash মিললে একবার আসল slice মিলিয়ে নাও (verify), তাহলে উত্তর সবসময় সঠিক।

আরও কম কাজে সমাধান

Pattern ও প্রথম window-এর hash বানাও। Hash মিললে slice verify করো; তারপর বাঁ অক্ষরের contribution বাদ, base দিয়ে গুণ, ডান অক্ষর যোগ, mod করো। Update O(1), কিন্তু verification O(m)। সব অক্ষর একই হলে অনেক সত্যিকারের match-ও বারবার verify হয়।

ভাবনার পরিবর্তন

মোচড়: string equality-কে integer equality-তে নামিয়ে আনো, আর সেই integer-কে window slide-এ incremental রাখো। এটাই Pattern 7-এর প্রাণ। CP-তে আরও একটা মোচড় জরুরি — base/mod randomize করো (বা double hashing), কারণ fixed parameter-কে anti-hash test case ইচ্ছে করে collide করায়। verify-step থাকলে এই গণনায় তা এমনিতেই নিরাপদ।

ছবিতে বোঝা

S = "aaa", P = "aa" (m=2, base=256); প্রতি window-এর hash roll হয়:

উদাহরণ
P-এর hash  : 'a'·256 + 'a'                     = h(P)
window[0:2]="aa": একই হিসাব = h(P)             → মেলে, যাচাই "aa"=="aa" ✓
roll → window[1:3]="aa":
   বাদ S[0]='a'·base^(m-1), ·base, যোগ S[2]='a' = h(P) আবার → মেলে ✓
উত্তর: 2

প্রতিটা roll-এ মাত্র কয়েকটা গাণিতিক ধাপ — পুরো substring আবার পড়া নয়।

ছোট input-এ ধাপে ধাপে

Input S = "aba", P = "ab" (base=256, m=2):

  1. P-hash = ord('a')·256 + ord('b')। window S[0:2]="ab"-এর hash = একই → মেলে; slice "ab"=="ab" → count = 1।
  2. roll: বাদ S[0]='a' (·high), ·256, যোগ S[2]='a' → window এখন "ba"-র hash।
  3. শুরু-position 1: window-hash == P-hash? "ba" != "ab" → hash আলাদা → count বাড়ে না।
  4. শেষ: count = 1।

কোড ও ব্যাখ্যা

Python

Python
def count_occurrences(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return 0
    base = 256                                  # alphabet-এর চেয়ে বড় base
    mod = 1_000_000_007                         # বড় prime, collision কমায়
    p_hash = 0                                  # pattern-এর hash
    for ch in pattern:
        p_hash = (p_hash * base + ord(ch)) % mod
    window_hash = 0                             # প্রথম window-এর hash
    for i in range(m):
        window_hash = (window_hash * base + ord(text[i])) % mod
    high = pow(base, m - 1, mod)                # সবচেয়ে বড় স্থানীয় মান
    count = 0
    for start in range(n - m + 1):
        if window_hash == p_hash:              # hash মিলেছে
            if text[start:start + m] == pattern:   # collision-গার্ড: আসল যাচাই
                count += 1
        if start < n - m:                      # পরের window-তে roll
            out_ch = ord(text[start])
            in_ch = ord(text[start + m])
            window_hash = ((window_hash - out_ch * high) * base + in_ch) % mod
    return count

# ---- tests ----
assert count_occurrences("abababab", "ab") == 4
assert count_occurrences("aaaaa", "aa") == 4
assert count_occurrences("abcdef", "xyz") == 0
assert count_occurrences("mississippi", "issi") == 2
assert count_occurrences("hello", "") == 0
print("সব test pass!")

কোডের প্রতিটি অংশ

  • if m == 0 or m > n: return 0 — খালি pattern বা text-এর চেয়ে বড় pattern-এর কোনো occurrence নেই।
  • base, mod — polynomial hashing-এর প্যারামিটার; বড় prime mod collision কমায়।
  • প্রথম for — pattern-কে base ভিত্তির positional সংখ্যা হিসেবে এক hash-এ গুটিয়ে নেয়।
  • দ্বিতীয় for — text-এর প্রথম m-অক্ষর window-এর hash, একইভাবে।
  • high = pow(base, m - 1, mod) — বাঁ-প্রান্তের অক্ষরের স্থানীয় মান, roll-এ বাদ দিতে লাগে।
  • if window_hash == p_hash: if text[start:start+m] == pattern: count += 1 — hash মিললে আসল slice মিলিয়ে নিশ্চিত হই (collision থাকলেও উত্তর নির্ভুল)।
  • window_hash = ((window_hash - out_ch * high) * base + in_ch) % mod — O(1) roll: বাঁ অক্ষর বাদ, এক ঘর বাঁয়ে সরাও, ডান অক্ষর যোগ; Python-এ % mod ঋণাত্মককেও ঠিক রাখে।

Output মিলিয়ে দেখা

"abababab","ab"-এ চারটা position-এ hash মেলে আর verify পাস → 4। "aaaaa","aa"-এ overlap সহ চারটা → 4। "abcdef","xyz"-এ কোনো hash মেলে না → 0। "mississippi","issi"-এ index 1 ও 4-এ "issi" → 2। খালি pattern → 0 (গার্ডেই বেরিয়ে যায়)। শেষে print: সব test pass!।

Exact O(n+m) বিকল্প: KMP

Judge-এর বড় input-এ collision ছাড়া linear matching চাইলে KMP ব্যবহার করা যায়। lps[i] হলো pattern-এর 0..i অংশে সবচেয়ে বড় proper prefix-এর দৈর্ঘ্য, যা suffix-ও। Mismatch হলে text-এ পিছিয়ে না গিয়ে এই তথ্য দিয়ে pattern-এর অবস্থান ঠিক করি।

P="aba" হলে lps=[0,0,1]। S="ababa"-এর সম্পূর্ণ scan:

text index অক্ষর match হওয়া prefix length count
0 a 1 0
1 b 2 0
2 a 3: record, তারপর lps[2]=1 1
3 b 2 1
4 a 3: record, তারপর lps[2]=1 2
Python
def count_kmp(text, pattern):
    if not pattern:
        return 0  # helper convention; CSES pattern is nonempty
    m = len(pattern)
    lps = [0] * m
    j = 0
    for i in range(1, m):
        while j and pattern[i] != pattern[j]:
            j = lps[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        lps[i] = j

    count = j = 0
    for ch in text:
        while j and ch != pattern[j]:
            j = lps[j - 1]
        if ch == pattern[j]:
            j += 1
        if j == m:
            count += 1
            j = lps[j - 1]  # preserve overlapping suffix
    return count

assert count_kmp("ababa", "aba") == 2
assert count_kmp("aaaaa", "aa") == 4
assert count_kmp("abcdef", "xyz") == 0
assert count_kmp("ab", "abc") == 0

প্রতিবার j বাড়ে বা fallback-এ কমে। মোট যতবার বাড়তে পারে, তার চেয়ে বেশি fallback হতে পারে না। তাই time O(n+m), অতিরিক্ত space O(m)। CSES-এ উপরের function-এর পরে যোগ করো:

Python
import sys
text = sys.stdin.readline().strip()
pattern = sys.stdin.readline().strip()
print(count_kmp(text, pattern))

খরচ ও সাধারণ ভুল

সময়

O(n+m+qm), যেখানে q হলো hash মিলে যাওয়া window-এর সংখ্যা। Worst case O(nm): অনেক সত্যিকারের match-ও প্রতিবার O(m) যাচাই লাগে। Randomization এই খরচ দূর করে না। Exact O(n+m) চাইলে নিচের KMP ব্যবহার করো।

অতিরিক্ত জায়গা

O(m) peak অতিরিক্ত memory: Python slice-verify সাময়িক m-অক্ষরের string বানায়। শুধু running hash state O(1)।

যে ভুলগুলো এড়াতে হবে

  • collision উপেক্ষা করা — শুধু hash মিললেই count বাড়ালে বিরল ভুল ম্যাচ; hash মিললে আসল slice একবার verify করো (বা double hashing)।
  • fixed base/mod ব্যবহার করা — CF-এর anti-hash test fixed parameter collide করায়; base/mod randomize করো।
  • roll-এ ঋণচিহ্ন বা high ভুল — high = base^(m-1); বিয়োগের পর % mod দিতে ভুলো না (Python ঋণাত্মক mod ঠিক রাখলেও অভ্যাস রাখা ভালো)।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: seen-set of windows (#19 Repeated DNA, Pattern 4)-এর "window = key" idea, এখানে key হলো O(1)-এ roll হওয়া polynomial hash (Pattern 7)। গণিতটা আসে math fundamentals-এর place-value ও modular arithmetic (../../01-math-based-programming-fundamentals/02-modular-arithmetic/) থেকে। সম্পূর্ণ teaser ../patterns.md-র Pattern 7-এ, পূর্ণ পাঠ https://cp-algorithms.com/string/string-hashing.html-এ।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Rolling hash / counting: string equality-কে integer hash equality-তে নামাও; window slide-এ hash O(1)-এ roll করো (বাঁ contribution বাদ, ·base, ডান যোগ, mod)। hash মিললে verify; CF-তে base/mod randomize।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "অনেক substring দ্রুত তুলনা / খোঁজা / গোনা" (বিশেষত CF-এর hashing tag) দেখলেই rolling hash মনে পড়বে — string = base-সংখ্যা, slide = O(1) roll, equality = hash তুলনা + verify। এটা Repeated DNA-র window-key idea-র পূর্ণ রূপ; গণিতটা place-value আর modular arithmetic। randomize আর verify — এই দুটো ভুললে CF-এ ধরা।

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