স্ট্রিং অ্যালগরিদম৯ মিনিট পড়া

কেএমপি অ্যালগরিদম (KMP Algorithm)

স্ট্রিং বা লেখা খোঁজার সময় কখনোই পিছনে ফিরবেন না — পুরনো জ্ঞান কাজে লাগিয়ে এগিয়ে যান
preprocessing:\(O(m)\)search:\(O(n)\)total:\(O(n+m)\)space:\(O(m)\)

কল্পনা করুন আপনি একটি বিশাল বইয়ে একটি নির্দিষ্ট শব্দ খুঁজছেন। আপনি শব্দের ৮টি অক্ষর মিলিয়ে ফেলেছেন, কিন্তু ৯ নম্বর অক্ষরে গিয়ে দেখলেন কোনো মিল নেই। সাধারণ পদ্ধতিতে আপনি আবার এক ধাপ এগিয়ে গোড়া থেকে খোঁজা শুরু করবেন। কিন্তু আপনি তো জানেন যে আগের ৮টি অক্ষর কী ছিল! সেই তথ্য কেন ফেলে দেবেন?

এটিই হলো Knuth-Morris-Pratt (KMP) অ্যালগরিদমের মূল কৌশল: একবার পড়া অক্ষর আর কখনোই দ্বিতীয়বার পড়বেন না। টেক্সট বা মূল লেখার পয়েন্টার সবসময় শুধু সামনের দিকেই এগোবে। শুরুতেই কাঙ্ক্ষিত শব্দটি (pattern) ভালো করে বিশ্লেষণ করে একটি failure function বা lps array তৈরি করে নেওয়া হয়, যার সাহায্যে \(O(n+m)\) সময়েই সব ম্যাচ খুঁজে পাওয়া যায়।

সাধারণ পদ্ধতির সমস্যা কী?

সাধারণ সার্চিংয়ে প্রতিটি পজিশনে প্যাটার্নটি বসিয়ে চেক করা হয়। যদি কোথাও অমিল পাওয়া যায়, তবে পুরো পরিশ্রম বাদ দিয়ে প্যাটার্নটিকে মাত্র ১ ঘর ডানে সরিয়ে আবার শুরু থেকে চেক করা হয়। সবচেয়ে খারাপ ক্ষেত্রে (যেমন: প্যাটার্ন "aaaaab", মূল লেখা "aaaaaa...") এটি \(O(n \times m)\) সময় নেয়, যা বড় ডেটার ক্ষেত্রে খুবই ধীরগতি সম্পন্ন।

ফেইলুর ফাংশন বা lps অ্যারে

কেএমপি পদ্ধতি শুরুতেই প্যাটার্নটি ব্যবহার করে lps অ্যারে (Longest Proper Prefix that is also a Suffix) তৈরি করে। এটি মূলত আমাদের বলে দেয়: আপনার প্যাটার্নের কোনো একটি অংশে অমিল হলে, আপনি প্যাটার্নটির ঠিক কোন অংশ থেকে আবার মেলানো শুরু করতে পারবেন যাতে আগে মেলা অক্ষরগুলো ফেলে দিতে না হয়।

উদাহরণ: প্যাটার্ন = "ABCABD"

  • lps[0] = 0 ("A")
  • lps[1] = 0 ("AB")
  • lps[2] = 0 ("ABC")
  • lps[3] = 1 ("ABCA" — শুরুতে এবং শেষে 'A' আছে)
  • lps[4] = 2 ("ABCAB" — শুরুতে এবং শেষে 'AB' আছে)
  • lps[5] = 0 ("ABCABD")

এই অ্যারেটি \(O(m)\) সময়েই তৈরি করা যায়।

সার্চ করার সময় lps-এর ব্যবহার

টেক্সট বা মূল লেখা এবং প্যাটার্ন মেলানোর সময় দুটি পয়েন্টার (i এবং j) ব্যবহার করা হয়:

  • যদি টেক্সট এবং প্যাটার্নের ক্যারেক্টার মিলে যায় (text[i] == pattern[j]): i এবং j দুটোকেই ১ ঘর বাড়ান। j যদি প্যাটার্নের শেষে পৌঁছে যায়, তবে একটি পূর্ণ ম্যাচ পাওয়া গেল।
  • যদি অমিল হয় এবং j > 0 থাকে: j-কে গোড়ায় না পাঠিয়ে j = lps[j-1] পজিশনে নিয়ে আসুন। মজার ব্যাপার হলো, পয়েন্টার i কিন্তু পিছিয়ে যাবে না! আমরা lps ভ্যালু ব্যবহার করে জানি যে প্যাটার্নের কতটুকু অংশ অলরেডি টেক্সটের সাথে মিলবে।
  • যদি একদম শুরুতে অর্থাৎ j == 0 তে অমিল হয়: তবে শুধু i এক ঘর বাড়ান।

এখানে মূল লেখার পয়েন্টার i কখনোই পিছনে ফিরে আসে না — প্রতিটি ক্যারেক্টার সর্বোচ্চ দুইবার চেক হয়। ফলে সার্চিং শেষ হয় মাত্র \(O(n)\) সময়ে।

কেন এটি কাজ করে?

যখন কোনো অমিল হয়, আমরা ইতিমধ্যে জানি যে আগের অক্ষরগুলো মিলে গিয়েছিল। lps ভ্যালু আমাদের সরাসরি বলে দেয় যে বর্তমান পজিশনের শেষে এমন কোনো অংশ আছে কি না যা প্যাটার্নের একদম শুরুর অংশের সাথে মিলে যায়। সেটুকু অংশকে পুনরায় চেক না করে আমরা সামনে থেকে কাজ চালিয়ে নিতে পারি।

দ্রষ্টব্য: পুরো অ্যালগরিদমের প্রাণ হলো এই ফেইলুর ফাংশন বা lps অ্যারে। একবার এটি সঠিকভাবে তৈরি করে ফেললে সার্চ করার কাজটা খুবই সহজ হয়ে যায়। এটি চমৎকারভাবে পুরনো পরিশ্রমকে পুনরায় ব্যবহার করতে সহায়তা করে।

কেএমপি অ্যালগরিদম — lps তৈরি এবং সার্চিং

def build_lps(pattern):
    m   = len(pattern)
    lps = [0] * m
    k   = 0  # length of current matching prefix
    for i in range(1, m):
        while k > 0 and pattern[k] != pattern[i]:
            k = lps[k-1]  # fall back to previous known match
        if pattern[k] == pattern[i]:
            k += 1
        lps[i] = k
    return lps


def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0: return []
    lps     = build_lps(pattern)
    matches = []
    j = 0  # number of characters matched in pattern
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = lps[j-1]
        if text[i] == pattern[j]:
            j += 1
        if j == m: # match found!
            matches.append(i - m + 1)
            j = lps[j-1]
    return matches


text    = "AABAACAADAABAABA"
pattern = "AABA"
print("lps array:", build_lps(pattern))
print("Matches found at indices:", kmp_search(text, pattern))
Output
lps: [0, 1, 0, 1]
Matches at: [0, 9, 12]

Complexity

🔨 lps তৈরি করা (Preprocessing)
প্যাটার্নটিকে একবার স্ক্যান করলেই এটি তৈরি হয়ে যায়
প্যাটার্ন দৈর্ঘ্যের সমানুপাতিক \(O(m)\)
🔍 কেএমপি সার্চ ফেজ
টেক্সট পয়েন্টার i কখনোই পিছনে ফিরে আসে না
মূল লেখার দৈর্ঘ্যের সমানুপাতিক \(O(n)\)
⚡ সর্বমোট সময় (build + search)
সাধারণ গুণের তুলনায় অনেক দ্রুত; বড় টেক্সট প্রসেসিংয়ের জন্য আদর্শ
প্যাটার্ন + টেক্সট দৈর্ঘ্য \(O(n+m)\)
💾 স্পেস বা মেমোরি
টেক্সটের সাইজ যত বড়ই হোক, মেমোরি শুধু প্যাটার্ন সাইজ অনুযায়ী লাগে
শুধু প্যাটার্নের দৈর্ঘ্যে সমান \(O(m)\)

ছোট কুইজ

প্যাটার্নের একটি নির্দিষ্ট পজিশন i এর জন্য lps[i] এর কাজ কী?

পড়া চালিয়ে যান