Z-অ্যালগরিদম

১ · Z-অ্যারের সংজ্ঞা

একটি স্ট্রিং $s$ (দৈর্ঘ্য $n$)-এর জন্য Z-অ্যারে $Z[0 \dots n-1]$ এভাবে সংজ্ঞায়িত: $$Z[i] = \text{দীর্ঘতম } k \text{ যেখানে } s[0 \dots k-1] = s[i \dots i+k-1]$$ অর্থাৎ $Z[i]$ হলো ইনডেক্স $i$ থেকে শুরু হওয়া সাবস্ট্রিং $s[i \dots]$ পুরো স্ট্রিং $s$-এর প্রিফিক্সের সাথে সর্বোচ্চ কতদূর পর্যন্ত মেলে, তার দৈর্ঘ্য। কনভেনশন অনুযায়ী $Z[0]$ সংজ্ঞায়িত করা হয় না (অথবা কখনও কখনও $0$ বা $n$ ধরা হয়, বাস্তবায়নভেদে) — কারণ পুরো স্ট্রিং তো নিজের প্রিফিক্সের সাথে ট্রিভিয়ালি সম্পূর্ণ মেলে; আমাদের বাস্তবায়নে আমরা $Z[0] = n$ ব্যবহার করব, যা সবচেয়ে সাধারণ কনভেনশন।

উদাহরণস্বরূপ, স্ট্রিং "aaabaab"-এর জন্য Z-অ্যারে হাতে-কলমে গণনা করা যাক (ইনডেক্স $0$ থেকে $6$):

• $Z[0] = 7$ (কনভেনশন অনুযায়ী পুরো দৈর্ঘ্য)
• $Z[1]$ — s[1..] = "aabaab", প্রিফিক্স "aaabaab"-এর সাথে তুলনা: "aa" মেলে (দুটোতেই "aa"), তৃতীয় ক্যারেক্টারে s[1+2]='b' বনাম s[2]='a' — মেলে না → $Z[1] = 2$
• $Z[2]$ — s[2..] = "abaab", প্রথম ক্যারেক্টার 'a' = s[0]='a' মেলে, দ্বিতীয় s[3]='b' বনাম s[1]='a' — মেলে না → $Z[2] = 1$
• $Z[3]$ — s[3..] = "baab", প্রথম ক্যারেক্টার 'b' বনাম s[0]='a' — একদমই মেলে না → $Z[3] = 0$
• $Z[4]$ — s[4..] = "aab", "aa" মেলে, তারপর s[4+2]='b' বনাম s[2]='a' — মেলে না → $Z[4] = 2$
• $Z[5]$ — s[5..] = "ab", প্রথম ক্যারেক্টার 'a' মেলে, দ্বিতীয় s[6]='b' বনাম s[1]='a' — মেলে না → $Z[5] = 1$
• $Z[6]$ — s[6..] = "b", প্রথম ক্যারেক্টার 'b' বনাম s[0]='a' — মেলে না → $Z[6] = 0$

অর্থাৎ "aaabaab"-এর Z-অ্যারে হলো [7, 2, 1, 0, 2, 1, 0] — নিচের কোড সেলে এই একই ফলাফল প্রোগ্রামগতভাবে গণনা করে হাতে-কলমের হিসাবের সাথে মিলিয়ে দেখানো হবে।

২ · [l, r] উইন্ডো কৌশল — কেন O(n)

উপরের হাতে-কলমের গণনায় প্রতিটি $Z[i]$-এর জন্য নতুন করে ক্যারেক্টার তুলনা করা হয়েছে — এটি নেইভভাবে করলে $O(n^2)$ সময় লাগত। Z-অ্যালগরিদমের কৌশল হলো এখন পর্যন্ত পাওয়া "সবচেয়ে ডানে বিস্তৃত মিল" মনে রাখা — একটি উইন্ডো $[l, r]$ যেখানে $s[l \dots r]$ একটি সাবস্ট্রিং যা $s$-এর প্রিফিক্সের সাথে মেলে এবং $r$ এখন পর্যন্ত দেখা সর্বোচ্চ ডান-সীমানা। নতুন ইনডেক্স $i \le r$ হলে, $i$-এর জন্য আগে থেকেই জানা তথ্য ($Z[i-l]$, কারণ $s[i \dots r]$ ইতিমধ্যে $s$-এর একটি প্রিফিক্সের অংশ হিসেবে প্রমাণিত) পুনর্ব্যবহার করা যায়: $$Z[i] = \min(r - i + 1,\ Z[i - l])$$ এবং এরপর $r$-এর বাইরেও মিল থাকলে সরাসরি ক্যারেক্টার তুলনা করে সম্প্রসারণ করা হয়। প্রতিটি ক্যারেক্টার তুলনা হয় এই সম্প্রসারণে $r$-কে সামনে ঠেলে দেয় (এবং $r$ কখনও পেছনে যায় না), তাই মোট তুলনার সংখ্যা $O(n)$ — KMP-এর $i$ পয়েন্টার কখনও পেছনে না যাওয়ার আর্গুমেন্টের সাথে কাঠামোগতভাবে সাদৃশ্যপূর্ণ একটি অ্যামর্টাইজড যুক্তি।

৩ · স্ট্রিং ম্যাচিং-এ প্রয়োগ

Z-অ্যারে সরাসরি প্যাটার্ন ম্যাচিং করে না — এটি একটি একক স্ট্রিং-এর নিজের প্রিফিক্সের সাথে সাদৃশ্য মাপে। তাই টেক্সট $T$-এ প্যাটার্ন $P$ খুঁজতে একটি চতুর কৌশল ব্যবহার করা হয়: একটি স্ট্রিং $P + \# + T$ তৈরি করা হয়, যেখানে $\#$ এমন একটি সেপারেটর ক্যারেক্টার যা $P$ বা $T$-এর কোনোটাতেই নেই। এই কনক্যাটেনেটেড স্ট্রিং-এর Z-অ্যারে বানিয়ে, যেখানে $Z[i] = |P|$ (প্যাটার্নের দৈর্ঘ্য), সেখানেই টেক্সটে একটি সম্পূর্ণ ম্যাচ পাওয়া গেছে বোঝায় — কারণ সেই পজিশন থেকে শুরু হওয়া সাবস্ট্রিং পুরো প্যাটার্নের সাথে হুবহু মিলেছে। সেপারেটরটি নিশ্চিত করে যে $Z[i]$ কখনও $|P|$-এর বেশি হতে পারবে না (সেপারেটরে গিয়ে মিল ভেঙে যাবে), তাই "$Z[i] = |P|$" মানেই "কমপক্ষে $|P|$" নয়, বরং "ঠিক $|P|$"।

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

নিচের কোডে প্রথমে Z-অ্যারে নির্মাণ করা হয়েছে এবং হাতে-কলমে গণনা করা "aaabaab"-এর ফলাফলের সাথে assert দিয়ে মিলিয়ে দেখা হয়েছে। এরপর প্যাটার্ন+সেপারেটর+টেক্সট কৌশল দিয়ে সম্পূর্ণ ম্যাচিং বাস্তবায়ন করে নেইভ বেসলাইনের বিপরীতে একাধিক এজ কেসে (খালি প্যাটার্ন, টেক্সটের চেয়ে বড় প্যাটার্ন, কোনো ম্যাচ না থাকা, পুরো টেক্সট জুড়ে ম্যাচ) যাচাই করা হয়েছে।

def build_z_array(s):
    # Z[i] = দীর্ঘতম উপসর্গ-দৈর্ঘ্য যা s[i..]-এর সাথে s-এর প্রিফিক্সের মেলে
    n = len(s)
    z = [0] * n
    if n == 0:
        return z
    z[0] = n   # কনভেনশন: পুরো স্ট্রিং নিজের প্রিফিক্সের সাথে সম্পূর্ণ মেলে
    l, r = 0, 0   # এখন পর্যন্ত পাওয়া সবচেয়ে ডানে বিস্তৃত Z-বক্স [l, r]
    for i in range(1, n):
        if i < r:
            # আগের Z-বক্সের ভেতরে -- পুরনো গণনা পুনর্ব্যবহার করো
            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]   # Z-বক্স সম্প্রসারিত হলো -- r কখনও পেছনে যায় না
    return z


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 z_match(text, pattern, sep="\x01"):
    # প্যাটার্ন + সেপারেটর + টেক্সট কনক্যাটেনেট করে Z-অ্যারে দিয়ে ম্যাচিং
    n, m = len(text), len(pattern)
    positions = []
    if m == 0 or m > n:
        return positions
    combined = pattern + sep + text
    z = build_z_array(combined)
    for i in range(m + 1, len(combined)):
        if z[i] == m:
            positions.append(i - m - 1)   # কম্বাইন্ড স্ট্রিং-এর ইনডেক্স থেকে টেক্সটের ইনডেক্সে রূপান্তর
    return positions


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

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

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

print(f"\nসব {len(tests)}টি টেস্ট কেসে (এজ কেসসহ) Z-অ্যালগরিদম ও নেইভ সম্পূর্ণ একমত।")