KMP অ্যালগরিদম

১ · সমস্যা — নেইভ ম্যাচিং কেন কাজ পুনরাবৃত্তি করে

L40-এ দেখা নেইভ ম্যাচিং একটি মিসম্যাচ পেলে টেক্সট পয়েন্টার $i$ মাত্র একধাপ এগিয়ে দিয়ে পুরো তুলনা প্রক্রিয়া নতুন করে শুরু করে ($j = 0$ থেকে)। কিন্তু যদি প্যাটার্নের একটি অংশ ইতিমধ্যে মিলে থাকে (যেমন প্যাটার্ন "ababaca"-এর প্রথম ৫টি ক্যারেক্টার "ababa" মিলে যাওয়ার পর ৬ষ্ঠ ক্যারেক্টারে মিসম্যাচ হয়), তাহলে সেই তথ্য ফেলে দিয়ে নতুন করে শুরু করাটা অপচয়। KMP এই মিলে-যাওয়া অংশের গঠন থেকে বুঝে নেয় প্যাটার্ন পয়েন্টার ঠিক কোথায় "ফিরে" যাওয়া উচিত — টেক্সট পয়েন্টারকে একবারও পেছনে না সরিয়ে।

২ · ফেইলিউর/LPS অ্যারে — সুনির্দিষ্ট সংজ্ঞা

প্যাটার্ন $P$ (দৈর্ঘ্য $m$)-এর জন্য LPS অ্যারে $\pi[0 \dots m-1]$ এভাবে সংজ্ঞায়িত: $$\pi[i] = \max\{\, k : k < i+1 \text{ এবং } P[0 \dots k-1] = P[i-k+1 \dots i] \,\}$$ সহজ ভাষায়: $\pi[i]$ হলো $P[0 \dots i]$ (অর্থাৎ প্যাটার্নের প্রথম $i+1$টি ক্যারেক্টার) উপসর্গের দীর্ঘতম প্রকৃত প্রিফিক্স-এর দৈর্ঘ্য যা একই সাথে সেই একই উপসর্গের একটি সাফিক্স ও বটে। "প্রকৃত প্রিফিক্স (proper prefix)" মানে পুরো স্ট্রিং নিজে বাদে যেকোনো প্রিফিক্স — অর্থাৎ $k < i+1$।

উদাহরণস্বরূপ, প্যাটার্ন "ababaca"-এর জন্য LPS অ্যারে হাতে-কলমে গণনা করা যাক:

• $\pi[0]$ — "a"-এর কোনো প্রকৃত প্রিফিক্স নেই (দৈর্ঘ্য ১ স্ট্রিং-এর প্রকৃত প্রিফিক্স শুধু খালি স্ট্রিং) → $\pi[0] = 0$
• $\pi[1]$ — "ab": প্রিফিক্স "a", সাফিক্স "b" — মেলে না → $\pi[1] = 0$
• $\pi[2]$ — "aba": প্রিফিক্স "a" = সাফিক্স "a" ✓ → $\pi[2] = 1$
• $\pi[3]$ — "abab": প্রিফিক্স "ab" = সাফিক্স "ab" ✓ → $\pi[3] = 2$
• $\pi[4]$ — "ababa": প্রিফিক্স "aba" = সাফিক্স "aba" ✓ → $\pi[4] = 3$
• $\pi[5]$ — "ababac": দীর্ঘতম মেলা প্রিফিক্স-সাফিক্স? "abac"-এর সাফিক্স "c"-এ শেষ, কিন্তু প্রিফিক্স "a"-এ শুরু — কোনো দৈর্ঘ্যেই মেলে না → $\pi[5] = 0$
• $\pi[6]$ — "ababaca": প্রিফিক্স "a" = সাফিক্স "a" ✓ (দৈর্ঘ্য ২ চেষ্টা করলে "ab" বনাম "ca" মেলে না) → $\pi[6] = 1$

অর্থাৎ "ababaca"-এর LPS অ্যারে হলো [0, 0, 1, 2, 3, 0, 1] — এটি একটি সুপরিচিত টেক্সটবুক উদাহরণ, এবং নিচের কোড সেলে এই একই ফলাফল প্রোগ্রামগতভাবে গণনা করে দেখানো হবে যাতে হাতে-কলমের হিসাব ও কোডের আউটপুট মিলে যায়।

৩ · LPS অ্যারে নির্মাণ — অ্যালগরিদম

LPS অ্যারে নিজেই একটি সুন্দর স্ব-নির্ভরশীল (self-referential) কৌশলে $O(m)$ সময়ে তৈরি করা যায় — প্যাটার্নকে নিজের সাথেই তুলনা করে। দুটি পয়েন্টার রাখা হয়: length (এখন পর্যন্ত পাওয়া মিলের দৈর্ঘ্য) এবং i (যে ইনডেক্সের $\pi$ মান গণনা করা হচ্ছে)। P[i] == P[length] হলে মিল বেড়ে যায় ($\pi[i] = $ length বাড়িয়ে); না মিললে, length != 0 হলে length-কে LPS[length - 1]-এ "পিছিয়ে" নেওয়া হয় (ঠিক যেভাবে সার্চের সময় মিসম্যাচে করা হবে — একই নীতি দুই জায়গাতেই কাজ করে), আর length == 0 হলে সরাসরি $\pi[i] = 0$ ধরে $i$ এগিয়ে যাওয়া হয়।

৪ · বাস্তবায়ন ও নেইভ বেসলাইনের বিপরীতে যাচাই

নিচের কোডে প্রথমে LPS অ্যারে নির্মাণ করা হয়েছে এবং হাতে-কলমে গণনা করা "ababaca"-এর ফলাফলের সাথে assert দিয়ে মিলিয়ে দেখা হয়েছে। এরপর সম্পূর্ণ KMP সার্চ বাস্তবায়ন করে L40-এর নেইভ ফাংশনের বিপরীতে একাধিক টেস্ট স্ট্রিং-এ (ওভারল্যাপিং ম্যাচসহ, যেমন "aaaa"-এ প্যাটার্ন "aa") যাচাই করা হয়েছে।

def build_lps(pattern):
    # LPS[i] = দীর্ঘতম প্রকৃত প্রিফিক্স যা pattern[0..i]-এর সাফিক্সও, তার দৈর্ঘ্য
    m = len(pattern)
    lps = [0] * m
    length = 0   # এখন পর্যন্ত পাওয়া মিলের দৈর্ঘ্য (আগের প্রিফিক্স-সাফিক্স)
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                # ঠিক সার্চের মতোই -- ছোট প্রিফিক্স-সাফিক্সে "ফিরে" যাও, i এগোয় না
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps


def naive_match(text, pattern):
    # L40-এর নেইভ বেসলাইন, রেফারেন্সের জন্য এখানে পুনরায় লেখা হলো
    n, m = len(text), len(pattern)
    positions = []
    if m == 0 or m > n:
        return positions
    for i in range(n - m + 1):
        match = True
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            positions.append(i)
    return positions


def kmp_match(text, pattern):
    n, m = len(text), len(pattern)
    positions = []
    if m == 0 or m > n:
        return positions
    lps = build_lps(pattern)
    i = j = 0   # i: টেক্সট পয়েন্টার (কখনও পেছনে যায় না), j: প্যাটার্ন পয়েন্টার
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                positions.append(i - j)   # সম্পূর্ণ প্যাটার্ন মিলেছে
                j = lps[j - 1]            # ওভারল্যাপিং ম্যাচ খোঁজার জন্য j-কে স্মার্টভাবে সরানো
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return positions


# --- হাতে-কলমে গণনা করা LPS অ্যারে যাচাই ---
lps_ababaca = build_lps("ababaca")
print("LPS('ababaca') =", lps_ababaca)
assert lps_ababaca == [0, 0, 1, 2, 3, 0, 1], "হাতে-কলমের হিসাবের সাথে মিলছে না!"
print("হাতে-কলমে গণনা করা [0, 0, 1, 2, 3, 0, 1]-এর সাথে সম্পূর্ণ মিলেছে।\n")

# --- KMP বনাম নেইভ, একাধিক টেস্ট কেসে ---
tests = [
    ("abababab", "aba"),
    ("aaaa", "aa"),          # ওভারল্যাপিং ম্যাচ
    ("aaaaaaaaaa", "aaa"),   # ওভারল্যাপিং ম্যাচ, দীর্ঘতর
    ("abcdefg", "xyz"),      # কোনো ম্যাচ নেই
    ("mississippi", "issi"),
    ("", "a"),               # খালি টেক্সট
    ("abc", ""),             # খালি প্যাটার্ন
    ("abc", "abcd"),         # প্যাটার্ন টেক্সটের চেয়ে বড়
    ("ababacaxxababaca", "ababaca"),
]

print(f"{'text':<20} | {'pattern':<10} | {'ম্যাচ পজিশন':<20} | মিলেছে?")
for text, pattern in tests:
    naive_pos = naive_match(text, pattern)
    kmp_pos = kmp_match(text, pattern)
    ok = (naive_pos == kmp_pos)
    print(f"{text:<20} | {pattern:<10} | {str(naive_pos):<20} | {'হ্যাঁ' if ok else 'না -- BUG!'}")
    assert naive_pos == kmp_pos, f"মিলছে না: {text!r}, {pattern!r}"

print(f"\nসব {len(tests)}টি টেস্ট কেসে (ওভারল্যাপিং ম্যাচসহ) KMP ও নেইভ সম্পূর্ণ একমত।")