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

জেড-অ্যালগরিদম (Z-Algorithm)

জেড-অ্যারে (Z-array): প্রতিটি অবস্থানে হিসাব মেলানোর দৈর্ঘ্য — লিনিয়ার প্যাটার্ন ম্যাচিং

Z-array build:দ্রুতগতিসম্পন্ন · O(n)pattern matching:দ্রুতগতিসম্পন্ন · O(n+m)space:O(n+m)

কল্পনা করুন আপনি একটি লম্বা ব্যানারে একটি শব্দ লিখেছেন। এবার আপনি ব্যানারের প্রতিটি অবস্থান বা পজিশনে দাঁড়িয়ে জিজ্ঞেস করছেন: "ব্যানারের শুরু থেকে ঠিক কতগুলো অক্ষর এখানের সাথে মিলে যাচ্ছে?" প্রতিটি স্থানে পাওয়া এই প্রশ্নের উত্তরকেই বলা হয় জেড-মান বা Z-value।

উদাহরণস্বরূপ, "aabxaa" স্ট্রিংটির ক্ষেত্রে:

অবস্থান 0 বা Position 0: এড়িয়ে যান (এটি শুরুর জায়গা)
অবস্থান 1: 'a' এর সাথে অবস্থান 0 এর 'a' মিলে যায়, এরপর 'a' এর সাথে 'b' মেলে না। তাই Z[1] = 1
অবস্থান 2: 'b' বনাম 'a' — কোনো মিল নেই। তাই Z[2] = 0
অবস্থান 3: 'x' বনাম 'a' — কোনো মিল নেই। তাই Z[3] = 0
অবস্থান 4: 'aa' প্রিফিক্স 'aa' এর সাথে মিলে যায়। তাই Z[4] = 2
অবস্থান 5: 'a' এর সাথে 'a' মেলে। তাই Z[5] = 1

সম্পূর্ণ জেড-অ্যারেটি (Z-array) দাঁড়ায় এমন: [_, 1, 0, 0, 2, 1]। একেবারে সহজ! আর সবচেয়ে মজার ব্যাপার হলো, আপনি পুরো অ্যারেটি স্রেফ একবার অতিক্রম করেই (one pass) হিসাব করতে পারবেন।

কেন সাধারণ নিয়মে প্রতিটি পজিশন চেক করা হয় না?

ব্রুট-ফোর্স বা সাধারণ পদ্ধতি — অর্থাৎ প্রতিটি অবস্থানে অক্ষর ধরে ধরে ম্যাচ করার চেষ্টা করা — সবচেয়ে চরম বা ওয়ার্স্ট কেসে O(n²) সময় নেয়। ধরুন "aaaaaaa" এর মতো একটি স্ট্রিংয়ের ক্ষেত্রে, প্রতিটি অবস্থান ডানদিকে একদম শেষ পর্যন্ত মিলতে থাকবে, ফলে আপনাকে n² সংখ্যক বার তুলনা করতে হবে।

জেড-অ্যালগরিদম একটি চমৎকার বুককিপিং বা হিসাব রাখার কৌশল ব্যবহার করে এটি এড়িয়ে যায়, যার নাম হলো জেড-বক্স (Z-box)।

জেড-বক্স (The Z-Box): পুরনো জানা জিনিস ফের ব্যবহার করা

আপনি যখন স্ট্রিংটির ডানদিকে হাঁটতে থাকবেন, আপনি সেই সর্বডানের বিরতি বা ইন্টারভ্যালটি (interval) [L, R] মনে রাখবেন যেখানে আপনি পূর্বেই একটি প্রিফিক্স ম্যাচ নিশ্চিত করেছেন। এই ইন্টারভ্যালটিকেই বলা হয় জেড-বক্স (Z-box)।

আপনি যখন জেড-বক্সের ভেতরের কোনো অবস্থান i তে থাকেন (যেখানে i ≤ R), আপনি আগে থেকেই জানেন যে S[i..R] স্ট্রিংটি S[i-L..R-L] এর সাথে মিলে যায় — কারণ এটি জেড-বক্সের নিয়মেই পড়ে। তাই আপনি কোনো নতুন অক্ষরের তুলনা না করেই Z[i] = min(Z[i-L], R-i+1) দিয়ে শুরু করতে পারেন!

তারপর আপনি R এর বাইরে মিলিয়ে দেখার চেষ্টা করেন। মূল কৌশলটি হলো: R সর্বদা কেবল ডানদিকেই এগোয়। আপনি যে অক্ষরগুলো তুলনা করেন সেগুলো হয় R কে ডানদিকে নিয়ে যায়, অথবা মিলানোর কাজ শেষ করে দেয়। সুতরাং সম্পূর্ণ স্ট্রিংজুড়ে, প্রতিটি অক্ষর সর্বাধিক কয়েকবারই (constant number of times) তুলনা করা হয় — যা মোট O(n) সময়ের মধ্যে কাজ শেষ করতে দেয়।

দ্রষ্টব্য: জেড-বক্স যেন একটি চিট শিটের (cheat sheet) মতো কাজ করে। একবার আপনি কোনো নির্দিষ্ট জায়গা পর্যন্ত প্রিফিক্স ম্যাচ নিশ্চিত করে ফেললে, আপনাকে আর ওই জায়গাটি পুনরায় পড়তে হবে না — আপনি কেবল পুরনো জানাশোনা কাজে লাগাবেন। R সর্বদা ডানদিকে যায়, তাই মোট কাজের পরিমাণ বা সময় O(n) এর মধ্যেই থাকে।

জেড-অ্যারে + প্যাটার্ন ম্যাচিং

def build_z(s):
    n = len(s)
    z = [0] * n
    L = R = 0
    for i in range(1, n):
        if i < R:
            z[i] = min(R - i, z[i - L])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > R:
            L, R = i, i + z[i]
    return z

def z_search(text, pattern):
    combined = pattern + '$' + text
    z = build_z(combined)
    m = len(pattern)
    return [i - m - 1 for i in range(m + 1, len(combined)) if z[i] >= m]

print(build_z("aabxaa"))          # [0, 1, 0, 0, 2, 1]
print(z_search("abcabcabc", "abc"))  # [0, 3, 6]

Output

[0, 1, 0, 0, 2, 1]
[0, 3, 6]

প্যাটার্ন ম্যাচিংয়ের জন্য জেড-এর ব্যবহার

এর কৌশলটি খুবই সুন্দর ও সহজ: pattern + '$' + text এভাবে পরপর বসিয়ে দিন, যেখানে '$' হলো এমন একটি অদ্ভুত অক্ষর যা কখনো ওই স্ট্রিং দুটোর মাঝে আসবে না। এই একত্রিত স্ট্রিংটির জেড-অ্যারে হিসাব করে ফেলুন।

এবার টেক্সট এর অংশের অবস্থানগুলোতে নজর দিন। যদি দেখেন Z[i] এর মান প্যাটার্নটির দৈর্ঘ্যের সমান বা বেশি, এর অর্থ হলো টেক্সটের ওই জায়গা থেকে শুরু হওয়া পুরো অংশটি প্যাটার্নের সাথে পুরোপুরি মিলে গেছে — তার মানে আপনি আপনার প্যাটার্নটি পেয়ে গেছেন!

মাঝখানে '$' দিয়ে আলাদা করাটা খুবই জরুরি: টেক্সটের শুরুতেই যদি প্যাটার্নের সমান অক্ষর থাকে, '$' নিশ্চিত করে যে জেড-এর মান কখনো প্যাটার্নের দৈর্ঘ্য বা m এর চেয়ে বেশি হবে না। এটি না দিলে, টেক্সটের প্রথম স্থানেই সব সময় প্রিফিক্সের দৈর্ঘ্যের সমান বড় মান দেখাত, যা ভুল পথে চালিত করতে পারে।

জেড-অ্যালগরিদম (Z-Algorithm) বনাম কেএমপি (KMP)

দুটি পদ্ধতিই O(n+m) সময়ে স্ট্রিং ম্যাচিংয়ের সমাধান দেয়। KMP একটি ফেইলিওর ফাংশন (failure function) তৈরি করে (এটি হলো দীর্ঘতম প্রপার প্রিফিক্স যা একই সাথে একটি সাফিক্সও বটে)। আর জেড-অ্যালগরিদম একটি জেড-অ্যারে তৈরি করে (প্রতিটি অবস্থানে দীর্ঘতম প্রিফিক্সের মিল)। এগুলো মূলত একটি স্ট্রিংয়ের প্রিফিক্স-সাফিক্স কাঠামোকে দেখার দুটি আলাদা দৃষ্টিকোণ।

অনেক প্রোগ্রামারদের কাছে Z বাস্তবায়ন করা বা কোড লেখা বেশি সোজা মনে হয় — কারণ এতে একটি মসৃণ জেড-বক্স ইনভ্যারিয়্যান্ট (Z-box invariant) থাকে এবং কোনো জটিল lps টেবিলের দরকার হয় না। তবে, KMP এর ফেইলিওর ফাংশনটি আহো-কোরাসিক (Aho-Corasick) এর মূল ভিত্তি, যা এটিকে মাল্টি-প্যাটার্ন বা একাধিক প্যাটার্নভিত্তিক খোঁজার অ্যালগরিদমের জন্য অনেক বেশি উপযোগী করে তোলে।