String matching — Rabin-Karp, KMP আর Z algorithm

১ · সমস্যাটি — লম্বা লেখার ভেতরে ছোট একটি টুকরো খোঁজা

ব্রাউজারে Ctrl+F চেপে “bKash” লিখলেন — পুরো পাতায় শব্দটি যেখানে যেখানে আছে, হলুদ হয়ে গেল। পর্ব ১১-এ (String) এই কাজের নাম দেখেছিলেন pattern matching: n দৈর্ঘ্যের একটি লেখা (text) T-এর ভেতরে m দৈর্ঘ্যের pattern P কোন কোন index থেকে হুবহু শুরু হয়, সব খুঁজে বের করা। ছোট শোনালেও এই প্রশ্নের পেছনে দাঁড়িয়ে আছে অনেক বড় বড় ব্যবস্থা:

সরল পদ্ধতি আর তার সবচেয়ে খারাপ ক্ষেত্র

পর্ব ১১-এর naive string matching মনে করুন: P-কে T-এর প্রতিটি সম্ভাব্য শুরুর ঘর s-এ (s = 0 থেকে n − m) বসিয়ে বাঁ থেকে অক্ষর মেলান, অমিল পেলেই পরের s. মোট n − m + 1টি shift, প্রতিটিতে সর্বোচ্চ m তুলনা — O(n·m). সাধারণ ইংরেজি লেখায় বেশিরভাগ shift প্রথম অক্ষরেই বাতিল হয়, তাই কাজ কম। কিন্তু worst case-টি দেখুন — T = aaaaaaaa (n = 8), P = aaab (m = 4):

T:      a a a a a a a a
s = 0:  a a a b            3 matches, then a != b   -> 4 comparisons
s = 1:    a a a b          again 3 matches + 1      -> 4
s = 2:      a a a b                                 -> 4
s = 3:        a a a b                               -> 4
s = 4:          a a a b                             -> 4
total = (n - m + 1) * m = 5 * 4 = 20 comparisons, 0 matches

প্রতিটি shift-এ আমরা আবার সেই একই aaa মিলিয়ে দেখি, যা আগের shift-এ ইতিমধ্যে জানা ছিল। n = 10⁶ আর m = 10⁵ হলে তুলনা প্রায় 9 × 10¹⁰ — কনটেস্টের ১–২ সেকেন্ডে অসম্ভব। m = n/2 নিলে (n/2 + 1)·(n/2) ≈ n²/4, অর্থাৎ Θ(n²). এই অপচয় দূর করার তিনটি ভিন্ন দর্শন এই পর্বের বিষয়:

এখানে n + m-এর চেয়ে ভালো করা সম্ভব নয়: সবচেয়ে খারাপ ক্ষেত্রে text-এর প্রায় প্রতিটি অক্ষর (অন্তত n − m + ১টি) না দেখলে নিশ্চিত হওয়া যায় না যে সেখানে মিল নেই, আর pattern-টি পুরো না পড়লে জানাই যায় না কী খুঁজছি। তাই O(n + m) মানে সর্বোত্তম — নিম্নসীমা Ω(n + m)-এর সমান।

২ · Rabin-Karp — জানালাকে একটি সংখ্যায় বদলানো

দোকানে মাল মেলানোর সময় অভিজ্ঞ দোকানি প্রতিটি বস্তা খুলে দেখেন না; আগে ওজন মেলান। ওজন না মিললে নিশ্চিত — এটা সেই বস্তা নয়। ওজন মিললে তবেই খুলে দেখেন, কারণ ভিন্ন জিনিসেরও ওজন সমান হতে পারে। Rabin-Karp অ্যালগরিদম ঠিক এভাবে চলে: প্রতিটি m দৈর্ঘ্যের জানালার একটি “ওজন” — hash — বের করে, আর শুধু hash মিললে অক্ষর ধরে যাচাই করে।

hash হিসেবে নেওয়া হয় polynomial hash: অক্ষরগুলোকে একটি base B-এর সংখ্যার অঙ্ক ধরে, একটি মৌলিক সংখ্যা M-এর ভাগশেষে (modular arithmetic):

আসল কৌশল rolling hash: জানালা এক ঘর ডানে সরালে পুরো hash নতুন করে হিসাব করতে হয় না। বাঁয়ের অক্ষরের অবদান (x_s·B^m−1) বাদ দিন, বাকিটা B দিয়ে গুণ করুন (সব অঙ্ক এক ঘর বাঁয়ে সরল), নতুন ডানের অক্ষর যোগ করুন:

B^m−1 mod M একবারই হিসাব করে রাখা যায়, তাই প্রতিটি সরানো O(1). হাতে হিসাবের সুবিধার জন্য খুব ছোট সংখ্যা নিচ্ছি: a = 1, b = 2, c = 3, B = 10, M = 13 — তখন hash হলো অঙ্কগুলো দিয়ে বানানো দশমিক সংখ্যাটির ১৩ দিয়ে ভাগশেষ। T = abccabc, P = abc; h(P) = 123 mod 13 = 6, আর B² mod 13 = 100 mod 13 = 9.

Pseudocode (0-based index)

RABIN-KARP(T, P, B, M):            // n = |T|, m = |P|, m <= n
    high = B^(m-1) mod M
    hp = hash(P);  hw = hash(T[0..m-1])
    for s = 0 to n - m:
        if hw == hp and T[s..s+m-1] == P:     // verify every hash hit
            report a match at s
        if s + m < n:
            hw = ((hw - T[s] * high) * B + T[s+m]) mod M

সময়ের হিসাব — “প্রত্যাশিত” কেন

প্রথম hash দুটি O(m), প্রতিটি roll O(1), মোট O(n + m). বাকি থাকে যাচাইয়ের খরচ: প্রতিটি hash মিলের জন্য O(m). base B যদি 0 থেকে M − 1-এর মধ্যে এলোমেলোভাবে বাছা হয়, তাহলে দুটি ভিন্ন m দৈর্ঘ্যের string-এর hash সমান হওয়া মানে একটি m − 1 মাত্রার বহুপদীর মূল হলো B — আর এমন মূল সর্বোচ্চ m − 1টি। তাই একটি জানালায় spurious hit-এর সম্ভাবনা ≤ (m − 1)/M, মোট প্রত্যাশিত spurious hit ≤ n·(m − 1)/M. M ≈ 10⁹ আর n·m ≤ 10⁹-এর মতো হলে এটি ১-এরও কম। ফলে expected running time:

এখানে occ = আসল মিলের সংখ্যা। শেষ পদটি বড় M-এ নগণ্য, তাই সাধারণ ক্ষেত্রে O(n + m). কিন্তু occ নিজেই বড় হতে পারে: T = aaaa…a আর P = aaa হলে প্রতিটি জানালা আসল মিল, প্রতিটিতে m তুলনা — Θ(n·m). তাই Rabin-Karp-এর সবচেয়ে খারাপ সময় O(n·m); শুধু “প্রথম মিল” চাইলে, বা যাচাই বাদ দিলে, এই সমস্যা থাকে না।

Double hashing, anti-hash test আর এলোমেলো base

একটি mod-এ M ≈ 10⁹ মানে প্রতিটি তুলনায় ভুলের সম্ভাবনা মোটামুটি 10⁻⁹. কিন্তু অনেক তুলনা হলে? ধরুন 10⁶টি substring-এর hash একটি set-এ রেখে “কয়টি আলাদা” গুনছেন। জোড়ার সংখ্যা প্রায় 5 × 10¹¹, আর birthday paradox-এর হিসাবে প্রায় √M ≈ 3 × 10⁴টি hash-এর পরেই অন্তত একটি collision-এর সম্ভাবনা ৫০%-এর কাছে পৌঁছায়। সমাধান double hashing: দুটি আলাদা মৌলিক mod (যেমন 10⁹ + 7 আর 998244353) দিয়ে দুটি hash, জোড়া হিসেবে তুলনা — কার্যত M ≈ 10¹⁸.

আরেকটি বিপদ ইচ্ছাকৃত। base আর mod যদি কোডে স্থির লেখা থাকে (যেমন B = 31, M = 2⁶⁴), প্রতিপক্ষ আগে থেকে এমন ইনপুট বানাতে পারে যার hash মিলে যায় — কনটেস্টের ভাষায় anti-hash test. Codeforces-এর মতো প্ল্যাটফর্মে hack-পর্যায়ে এভাবে বহু সমাধান ভাঙা হয়েছে; পর্ব ১১-এর ভাবনার প্রশ্নে Thue–Morse ক্রমের উদাহরণ দেখেছেন, যা 2⁶⁴ mod-এ যেকোনো বিজোড় base-এর hash ভাঙে। প্রচলিত প্রতিরক্ষা: বড় মৌলিক mod, আর base প্রোগ্রাম চলার সময় এলোমেলোভাবে বাছা (যেমন সময় বা random_device থেকে)। তখন খারাপ test আগে থেকে বানানো যায় না। hash function আর hash table-এর দিক থেকে collision-এর আলোচনা পর্ব ৩২ (Hash table)-এ।

৩ · KMP-এর মূল ধারণা — border আর prefix function

সরল পদ্ধতির অপচয় মনে করুন: P = abab দিয়ে খুঁজতে গিয়ে aba মিলিয়ে চতুর্থ অক্ষরে অমিল হলো। আমরা তখন জানি text-এর শেষ তিনটি অক্ষর aba. P-কে এক ঘর সরালে শুরু হবে ba…-র সাথে ab… তুলনা — নিশ্চিত অমিল, তুলনা না করেই জানা। দুই ঘর সরালে a-র নিচে a — মিল নিশ্চিত, আবার মেলানোর দরকার নেই। অর্থাৎ, কতদূর সরানো নিরাপদ আর কতটুকু আগে থেকেই মেলানো আছে, তা শুধু pattern-এর ওপর নির্ভর করে, text-এর ওপর নয়। তাই সেটি আগে একবার হিসাব করে রাখা যায়। এটিই Knuth–Morris–Pratt (KMP) অ্যালগরিদমের মূল কথা।

যা হিসাব করে রাখতে হবে তার নাম border: একটি string-এর এমন অংশ যা একই সাথে তার prefix আর suffix, কিন্তু পুরো string নয়। ababa-র border দুটি — a আর aba. abc-এর কোনো (খালি ছাড়া) border নেই। এবার সংজ্ঞা:

π কীভাবে O(m)-এ বানানো যায়

দুটি পর্যবেক্ষণই যথেষ্ট। (১) s[0..i]-এর একটি border-এর শেষ অক্ষর বাদ দিলে সেটি s[0..i−1]-এর একটি border. তাই s[0..i]-এর border খুঁজতে s[0..i−1]-এর border-গুলো নিয়ে দেখতে হয়, কোনটির পরের অক্ষর s[i]-এর সমান। (২) s[0..i−1]-এর সব border একটি শিকলে পাওয়া যায়: সবচেয়ে লম্বাটি k₁ = π[i−1], তার পরেরটি π[k₁ − 1], তার পরেরটি π[π[k₁ − 1] − 1]… কারণ একটি border-এর border-ও মূল string-এর border, আর দ্বিতীয় সবচেয়ে লম্বা border অবশ্যই সবচেয়ে লম্বাটির border. তাই অ্যালগরিদম: k = π[i−1] থেকে শুরু; s[i] ≠ s[k] হলে k = π[k − 1] করে পিছিয়ে যাওয়া; মিললে π[i] = k + 1, k শূন্যে পৌঁছেও না মিললে π[i] = 0. নিচে s = ababaca:

কেন O(m)? k প্রতিটি i-তে সর্বোচ্চ ১ বাড়ে, তাই মোট বাড়া ≤ m − 1. প্রতিটি “পিছিয়ে যাওয়া” (k = π[k − 1]) k-কে অন্তত ১ কমায় (π[k − 1] < k), আর k কখনো ঋণাত্মক হয় না। যতটুকু উঠেছে তার বেশি নামা যায় না — তাই মোট পিছিয়ে যাওয়া ≤ m − 1, সব মিলিয়ে O(m). ধাপ ৬-এ এক i-তেই তিনটি তুলনা হয়েছে, কিন্তু তার আগে ধাপ ৩–৫-এ k তিনবার বেড়ে সেই “পুঁজি” জমিয়ে রেখেছিল। এই হিসাবটিই পরের অংশে KMP-এর মূল প্রমাণ।

Pseudocode (0-based index)

PREFIX-FUNCTION(s):                // m = |s|
    pi[0] = 0
    for i = 1 to m - 1:
        k = pi[i - 1]                          // longest border of s[0..i-1]
        while k > 0 and s[i] != s[k]:
            k = pi[k - 1]                      // next shorter border
        if s[i] == s[k]: k = k + 1
        pi[i] = k
    return pi

৪ · KMP দিয়ে খোঁজা — text-এ কখনো পিছিয়ে না গিয়ে

খোঁজার অংশটি হুবহু একই লুপ, শুধু s[i]-এর জায়গায় text-এর অক্ষর T[i]. একটি সংখ্যা k রাখি: “এই মুহূর্তে P-এর প্রথম k অক্ষর T-এর সদ্য পড়া শেষ k অক্ষরের সাথে মিলে আছে”। নতুন অক্ষর T[i] এলে: মিললে k বাড়ে; না মিললে k = π[k − 1] করে ছোট border-এ নামি (অর্থাৎ P-কে ডানে সরাই) — text-এর index i কখনো পেছায় না। k = m হলে মিল পাওয়া গেল, শুরু i − m + 1, আর পরের (overlap করা) মিল খুঁজতে k = π[m − 1].

P = abab (π = 0 0 1 2), T = abaababab:

O(n + m)-এর প্রমাণ — potential যুক্তি

লুপের ভেতরে আরেকটি while লুপ — দেখে মনে হয় O(n·m). আসলে নয়, আর প্রমাণটি পরীক্ষায় প্রায়ই চাওয়া হয়। Amortized analysis-এর ভাষায় একটি potential function নিই: Φ = k (এই মুহূর্তে মিলে থাকা দৈর্ঘ্য)।

• শুরুতে Φ = 0, আর সবসময় Φ ≥ 0.
• প্রতিটি text-এর অক্ষরে বাইরের লুপ একবার চলে; সেখানে k সর্বোচ্চ ১ বাড়ে। তাই পুরো চালানোয় Φ মোট বাড়ে ≤ n.
• প্রতিটি “পিছানো” (k = π[k − 1]) Φ-কে অন্তত ১ কমায়, কারণ π[k − 1] ≤ k − 1. মিলের পরের k = π[m − 1]-ও কমায়।
• Φ শুরু হয়েছে 0-তে, কখনো ঋণাত্মক হয়নি, তাই মোট কমা ≤ মোট বাড়া ≤ n. অর্থাৎ পুরো চালানোয় while লুপ মোট n বারের বেশি চলে না।

সুতরাং খোঁজার অংশে মোট তুলনা ≤ 2n, আর π বানাতে একই যুক্তিতে ≤ 2m. KMP = Θ(n + m) সময়, O(m) বাড়তি জায়গা (শুধু π অ্যারে) — সবচেয়ে খারাপ ক্ষেত্রেও। অ্যালগরিদমের শুদ্ধতার যুক্তি (loop invariant, পর্ব ০৩): প্রতিটি ধাপের পরে k হলো “P-এর এমন সবচেয়ে লম্বা prefix, যা T[0..i]-এর একটি suffix”. কোনো মিল হারায় না, কারণ border শিকলের বাইরে কোনো দৈর্ঘ্য এই শর্ত মানতে পারে না — π বানানোর পর্যবেক্ষণ (২)-এর হুবহু পুনরাবৃত্তি।

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> prefixFunction(const string& p) {
    vector<int> pi(p.size(), 0);
    for (size_t i = 1; i < p.size(); ++i) {
        int k = pi[i - 1];                           // longest border so far
        while (k > 0 && p[i] != p[k]) k = pi[k - 1]; // fall back to a shorter border
        if (p[i] == p[k]) ++k;
        pi[i] = k;
    }
    return pi;
}

vector<int> kmpSearch(const string& t, const string& p, long long& steps) {
    vector<int> pi = prefixFunction(p), found;
    int k = 0;                                       // chars of p matched now
    for (int i = 0; i < (int)t.size(); ++i) {
        while (k > 0 && t[i] != p[k]) { k = pi[k - 1]; ++steps; }
        ++steps;
        if (t[i] == p[k]) ++k;
        if (k == (int)p.size()) { found.push_back(i - k + 1); k = pi[k - 1]; }
    }
    return found;
}

int main() {
    string p = "ababaca", t = "abababacababacababaca";
    long long steps = 0;
    cout << "pi(" << p << ") =";
    for (int v : prefixFunction(p)) cout << ' ' << v;
    cout << "\nmatches of " << p << " in " << t << ":";
    for (int s : kmpSearch(t, p, steps)) cout << ' ' << s;
    long long n = 100000, m = 1000;                  // naive worst case: a^n vs a^(m-1)b
    steps = 0;
    auto found = kmpSearch(string(n, 'a'), string(m - 1, 'a') + "b", steps);
    cout << "\nn=" << n << " m=" << m << ": matches=" << found.size() << ", kmp steps=" << steps
         << ", naive comparisons=" << (n - m + 1) * m << '\n';
}

pi(ababaca) = 0 0 1 2 3 0 1
matches of ababaca in abababacababacababaca: 2 8 14
n=100000 m=1000: matches=0, kmp steps=199001, naive comparisons=99001000

def prefix_function(p):
    pi = [0] * len(p)
    for i in range(1, len(p)):
        k = pi[i - 1]                    # longest border so far
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]                # fall back to a shorter border
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

def kmp_search(t, p):
    pi, found, k, steps = prefix_function(p), [], 0, 0
    for i, c in enumerate(t):            # k = chars of p matched now
        while k > 0 and c != p[k]:
            k, steps = pi[k - 1], steps + 1
        steps += 1
        if c == p[k]:
            k += 1
        if k == len(p):
            found.append(i - k + 1)      # match ends at i
            k = pi[k - 1]
    return found, steps

p, t = "ababaca", "abababacababacababaca"
print(f"pi({p}) =", *prefix_function(p))
print(f"matches of {p} in {t}:", *kmp_search(t, p)[0])
n, m = 100000, 1000                      # naive worst case: a^n vs a^(m-1)b
found, steps = kmp_search("a" * n, "a" * (m - 1) + "b")
print(f"n={n} m={m}: matches={len(found)}, kmp steps={steps}, "
      f"naive comparisons={(n - m + 1) * m}")

pi(ababaca) = 0 0 1 2 3 0 1
matches of ababaca in abababacababacababaca: 2 8 14
n=100000 m=1000: matches=0, kmp steps=199001, naive comparisons=99001000

৫ · Z algorithm — প্রতিটি ঘর থেকে prefix কতদূর মেলে

আরেকটি টেবিল, আরেকটু সরাসরি অর্থে। একটি string s-এর Z-array: z[i] = s আর s[i..]-এর সবচেয়ে লম্বা সাধারণ prefix-এর দৈর্ঘ্য (z[0] সাধারণত 0 বা n ধরা হয়, ব্যবহার হয় না)। যেমন s = aabxaab-এ z[4] = 3, কারণ index 4 থেকে aab শুরু, যা s-এর প্রথম তিন অক্ষর।

খোঁজার কৌশল: s = P + '$' + T বানান, যেখানে '$' একটি separator character — P বা T কোনোটিতেই নেই। তাহলে কোনো z মান m ছাড়াতে পারে না ('$'-এ এসে মিল থামবেই), আর T-এর অংশে যেখানে z[i] = m, সেখানে P পুরোটা মিলেছে — text-এ শুরু i − m − 1.

দ্রুত বানানোর কৌশল — Z-box: এ পর্যন্ত পাওয়া সবচেয়ে ডানে শেষ হওয়া মিলের অংশ [l, r) মনে রাখি; s[l..r−1] হুবহু s[0..r−l−1]-এর কপি। নতুন i যদি এই বাক্সের ভেতরে পড়ে (i < r), তাহলে s[i..] শুরুটা আসলে s[i−l..]-এর কপি — তাই z[i] অন্তত min(r − i, z[i − l]), বিনা তুলনায়। এর পর শুধু r-এর বাইরে অক্ষর মিলিয়ে বাড়াই। নিচে P = aab, T = baabaa, s = aab$baabaa:

কেন O(n)? প্রতিটি i-তে তুলনা দুই রকম। ব্যর্থ তুলনা প্রতি i-তে সর্বোচ্চ একটি (সেটিতেই লুপ থামে) — মোট ≤ n. সফল তুলনা: ধার করা মান যদি z[i − l] < r − i হয়, তাহলে পরের তুলনাটি নিশ্চিত ব্যর্থ (কপির ভেতরেই অমিল আছে), সফল একটিও নয়। অন্য সব ক্ষেত্রে মেলানো শুরু হয় r বা তার পরে, আর প্রতিটি সফল তুলনা নতুন r-কে এক ঘর ডানে ঠেলে। r কখনো কমে না আর n-এর বেশি যায় না — তাই সফল তুলনা মোট ≤ n. সব মিলিয়ে Z-array O(n) সময়ে, O(n) জায়গায়; খোঁজায় n + m + 1 দৈর্ঘ্যের s-এ, তাই O(n + m).

৬ · তিন পদ্ধতি পাশাপাশি — একই ইনপুটে একই উত্তর

নতুন অ্যালগরিদম লিখলে প্রথম কাজ: একটি সহজ, নিশ্চিতভাবে সঠিক brute force-এর সাথে মিলিয়ে দেখা। নিচের প্রোগ্রাম তিনটি ইনপুটে সরল পদ্ধতি, Rabin-Karp (দুটি mod: খুব ছোট 13 আর বড় 10⁹ + 7) আর Z algorithm চালিয়ে মিলগুলো তুলনা করে, সাথে spurious hit গোনে:

#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

vector<int> rabinKarp(const string& t, const string& p, long long B, long long M, int& spurious) {
    int n = t.size(), m = p.size(); vector<int> found;
    auto v = [](char c) { return c - 'a' + 1; };        // a = 1, b = 2, c = 3, ...
    long long hp = 0, hw = 0, high = 1;                  // high = B^(m-1) mod M
    for (int i = 0; i < m; ++i) hp = (hp * B + v(p[i])) % M, hw = (hw * B + v(t[i])) % M;
    for (int i = 1; i < m; ++i) high = high * B % M;
    for (int s = 0; s + m <= n; ++s) {
        if (hw == hp && t.compare(s, m, p) == 0) found.push_back(s);  // hash hit: verify
        else if (hw == hp) ++spurious;                   // same hash, different text
        if (s + m < n) hw = (((hw - v(t[s]) * high) % M + M) * B + v(t[s + m])) % M;  // roll
    }
    return found;
}

vector<int> zSearch(const string& t, const string& p) {
    string s = p + "$" + t;                              // '$' is in neither string
    int n = s.size(), m = p.size(), l = 0, r = 0;
    vector<int> z(n, 0), found;
    for (int i = 1; i < n; ++i) {
        if (i < r) z[i] = min(r - i, z[i - l]);          // reuse the Z-box [l, r)
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        if (i + z[i] > r) l = i, r = i + z[i];
        if (z[i] == m) found.push_back(i - m - 1);
    }
    return found;
}

int main() {
    for (auto [t, p] : vector<pair<string, string>>{{"abccabc", "abc"}, {"aaaaa", "aa"}, {"abababab", "aba"}}) {
        vector<int> naive;                               // brute force for reference
        for (int s = 0; s + (int)p.size() <= (int)t.size(); ++s)
            if (t.compare(s, p.size(), p) == 0) naive.push_back(s);
        int sp13 = 0, spBig = 0;
        auto rk13 = rabinKarp(t, p, 10, 13, sp13), rkBig = rabinKarp(t, p, 131, 1000000007, spBig);
        bool same = naive == rk13 && naive == rkBig && naive == zSearch(t, p);
        cout << t << " / " << p << " -> matches:"; for (int s : naive) cout << ' ' << s;
        cout << " | spurious M=13: " << sp13 << ", M=1e9+7: " << spBig
             << " | rk, z vs naive: " << (same ? "same" : "DIFFERENT") << '\n';
    }
}

abccabc / abc -> matches: 0 4 | spurious M=13: 1, M=1e9+7: 0 | rk, z vs naive: same
aaaaa / aa -> matches: 0 1 2 3 | spurious M=13: 0, M=1e9+7: 0 | rk, z vs naive: same
abababab / aba -> matches: 0 2 4 | spurious M=13: 3, M=1e9+7: 0 | rk, z vs naive: same

def rabin_karp(t, p, B, M):              # returns (matches, spurious hits)
    n, m = len(t), len(p)
    v = lambda c: ord(c) - ord('a') + 1
    hp = hw = 0
    for i in range(m):
        hp, hw = (hp * B + v(p[i])) % M, (hw * B + v(t[i])) % M
    high, found, spurious = pow(B, m - 1, M), [], 0   # high = B^(m-1) mod M
    for s in range(n - m + 1):
        if hw == hp:                     # hash hit: verify char by char
            if t[s:s + m] == p: found.append(s)
            else: spurious += 1
        if s + m < n:                    # drop t[s], add t[s+m]
            hw = ((hw - v(t[s]) * high) * B + v(t[s + m])) % M
    return found, spurious

def z_search(t, p):
    s = p + "$" + t                      # '$' is in neither string
    z, l, r = [0] * len(s), 0, 0
    for i in range(1, len(s)):
        if i < r: z[i] = min(r - i, z[i - l])   # reuse the Z-box [l, r)
        while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]: z[i] += 1
        if i + z[i] > r: l, r = i, i + z[i]
    return [i - len(p) - 1 for i in range(len(s)) if z[i] == len(p)]

for t, p in [("abccabc", "abc"), ("aaaaa", "aa"), ("abababab", "aba")]:
    naive = [s for s in range(len(t) - len(p) + 1) if t[s:s + len(p)] == p]
    rk13, sp13 = rabin_karp(t, p, 10, 13)
    rk_big, sp_big = rabin_karp(t, p, 131, 1000000007)
    same = naive == rk13 == rk_big == z_search(t, p)
    print(f"{t} / {p} -> matches:", *naive, end="")
    print(f" | spurious M=13: {sp13}, M=1e9+7: {sp_big}"
          f" | rk, z vs naive: {'same' if same else 'DIFFERENT'}")

abccabc / abc -> matches: 0 4 | spurious M=13: 1, M=1e9+7: 0 | rk, z vs naive: same
aaaaa / aa -> matches: 0 1 2 3 | spurious M=13: 0, M=1e9+7: 0 | rk, z vs naive: same
abababab / aba -> matches: 0 2 4 | spurious M=13: 3, M=1e9+7: 0 | rk, z vs naive: same

৭ · প্রয়োগ — period, compression আর আরও দ্রুত লাফ

String-এর period আর “একটি টুকরোর পুনরাবৃত্তি কি না”

p হলো s-এর একটি period, যদি সব বৈধ i-তে s[i] = s[i + p] — অর্থাৎ s-কে p ঘর সরালে নিজের সাথে মেলে। একটি সুন্দর তথ্য: p একটি period ⇔ দৈর্ঘ্য n − p-এর একটি border আছে (s[0..n−p−1] = s[p..n−1] — দুটি একই কথা)। তাই সবচেয়ে লম্বা border থেকে সবচেয়ে ছোট period:

আর s কোনো ছোট টুকরো t-এর পুরোপুরি পুনরাবৃত্তি (s = t t … t) হবে ঠিক তখন, যখন p < n আর p দিয়ে n নিঃশেষে বিভাজ্য। abcabcabc: π[8] = 6, p = 9 − 6 = 3, 9 % 3 = 0 → abc × ৩. abcabca: π[6] = 4, p = 3, কিন্তু 7 % 3 ≠ 0 → period 3 থাকলেও পূর্ণ পুনরাবৃত্তি নয়। ইন্টারভিউর “repeated substring pattern” প্রশ্নটি এভাবে O(n)-এ শেষ। একই ধারণায় compression যাচাই: লগ-ফাইলের একটি লাইন যদি একটি ছোট নকশার পুনরাবৃত্তি হয়, শুধু নকশা আর পুনরাবৃত্তির সংখ্যা রাখলেই চলে।

প্রতিটি prefix কতবার আছে

π দিয়ে আরও একটি ক্লাসিক কাজ: s-এর প্রতিটি দৈর্ঘ্যের prefix s-এর ভেতরে মোট কতবার আছে। প্রথমে প্রতিটি i-তে cnt[π[i]] এক বাড়ান; তারপর দৈর্ঘ্য n − 1 থেকে 1 পর্যন্ত নেমে cnt[π[k − 1]] += cnt[k] (একটি border-এর border-ও সেখানে আছে); শেষে প্রতিটি দৈর্ঘ্যে ১ যোগ (prefix-টি নিজে)। মোট O(n). শুধু P কতবার T-এ আছে জানতে চাইলে KMP-র মিলগুলো গুনলেই হয় — overlap-সহ।

৮ · বাংলা লেখায় খোঁজা আর অ্যালগরিদমগুলোর ইতিহাস

KMP, Z বা Rabin-Karp যেকোনো সংকেতের সারিতে কাজ করে — বাইট, code point, এমনকি শব্দ। প্রশ্ন হলো কোন সারিতে চালাচ্ছেন। পর্ব ১১-এ দেখেছেন, বাংলা লেখার তিনটি “দৈর্ঘ্য” আছে: UTF-8 বাইট, code point আর চোখে দেখা অক্ষর বা grapheme cluster. খোঁজায় এর তিনটি বাস্তব প্রভাব:

• বাইট ধরে খোঁজা নিরাপদ, কিন্তু index বাইটে। UTF-8-এর নকশায় শুরুর বাইট আর ধারাবাহিক বাইট আলাদা দেখতে, তাই একটি বৈধ UTF-8 pattern বৈধ UTF-8 text-এ কখনো একটি অক্ষরের মাঝখান থেকে মেলে না। C++-এ std::string-এ KMP চালালে মিল ঠিকই পাবেন — কিন্তু "কলম"-এ "ম"-এর অবস্থান আসবে 6 (বাইট), Python-এর str.find দেবে 2 (code point). দুটি সংখ্যা মিশিয়ে ফেললেই bug.
• Code point-এর মিল মানে চোখের মিল নয়। "ক্ষমা"-য় "ক" খুঁজলে মিল পাবেন, কারণ যুক্তাক্ষর ক্ষ = ক + ্ + ষ. ব্যবহারকারী কিন্তু “ক” অক্ষরটি সেখানে দেখেন না। প্রয়োজনে মিলের দুই প্রান্ত grapheme-এর সীমানায় পড়ছে কি না যাচাই করুন।
• একই দেখতে, ভিন্ন বাইট। ড় একটি code point হিসেবে, আবার ড + নুক্তা হিসেবেও লেখা যায়। খোঁজার আগে text আর pattern দুটিকেই একই রূপে আনুন — Unicode normalization (যেমন NFC). না হলে অ্যালগরিদম নির্ভুল হয়েও “পাওয়া যায়নি” বলবে।

Rabin-Karp-এ আরেকটি সূক্ষ্ম দিক: বাইটে hash করলে প্রতিটি সংকেত 0–255, code point-এ করলে 0 থেকে প্রায় ১১ লাখ — স্থির base নিলে B-কে সংকেতের সর্বোচ্চ মানের চেয়ে বড় রাখুন, নইলে ভিন্ন string-এর মধ্যে নিয়মিত (এলোমেলো নয়) collision তৈরি হয়।

৯ · AI-এর যুগে string matching — off-by-one আর অপ্রমাণিত দাবি

KMP বা Z-এর কোড AI মুহূর্তে লিখে দেয়, আর সাধারণ উদাহরণে প্রায় সবসময় ঠিক চলে। ভুল লুকিয়ে থাকে সূক্ষ্ম জায়গায়: π-র সূচক এক ঘর সরানো (π[k] বনাম π[k − 1]), মিলের পর k রিসেট করতে ভুলে যাওয়া (তখন overlap করা মিল হারায়), Z-box-এ [l, r] বনাম [l, r) গুলিয়ে ফেলা, আর C++-এ ঋণাত্মক mod. সবচেয়ে বিপজ্জনক হলো আত্মবিশ্বাসী complexity দাবি — “Rabin-Karp সবসময় O(n + m)”.

String matching-এ AI সাধারণত যেসব ভুল করে

AI-এর (বা নিজের) string matching কোড যাচাইয়ের চেকলিস্ট

• ছোট একটি pattern-এর π বা Z-array হাতে বের করে প্রোগ্রামের ছাপা মানের সাথে মিলিয়েছি
• overlap করা মিল (aaaaa / aa), কোনো মিল নেই, আর m > n — তিনটিতেই চালিয়েছি
• সরল brute force-এর সাথে হাজারখানেক এলোমেলো ছোট ইনপুটে (২–৩ অক্ষরের বর্ণমালায়) stress test করেছি
• worst case (aaa…a / aa…ab) দিয়ে n দ্বিগুণ করে সময় মেপেছি — দ্বিগুণ হলে রৈখিক
• Rabin-Karp-এ hash মিলের পর যাচাই আছে কি না, না থাকলে দুটি mod আর এলোমেলো base আছে কি না দেখেছি
• বাংলা বা Unicode ইনপুট হলে index বাইটে না code point-এ, আর normalization লাগবে কি না ঠিক করেছি