লংগেস্ট কমন সাবসিকোয়েন্স

১ · সমস্যার সংজ্ঞা

একটি সাবসিকোয়েন্সSubsequenceমূল স্ট্রিং থেকে কিছু ক্যারেক্টার (শূন্য বা তার বেশি) মুছে ফেলে গঠিত স্ট্রিং, কিন্তু অবশিষ্ট ক্যারেক্টারগুলোর আপেক্ষিক ক্রম অপরিবর্তিত থাকে। যেমন "ACE" হলো "ABCDE"-এর একটি সাবসিকোয়েন্স। সাবস্ট্রিং থেকে ভিন্ন — সাবস্ট্রিংয়ে ক্যারেক্টারগুলো পাশাপাশি (কনটিগুয়াস) থাকতে হয়, সাবসিকোয়েন্সে তা লাগে না। দুটি স্ট্রিং $X$ (দৈর্ঘ্য $m$) ও $Y$ (দৈর্ঘ্য $n$) দেওয়া থাকলে, লক্ষ্য এমন একটি স্ট্রিং খুঁজে বের করা যা $X$ ও $Y$ উভয়েরই সাবসিকোয়েন্স এবং যতটা সম্ভব দীর্ঘ — আমাদের শুধু তার দৈর্ঘ্য বের করলেই যথেষ্ট (এটাই এই পাঠের কোডের লক্ষ্য; পুরো সাবসিকোয়েন্সটি পুনর্গঠনের কৌশল DSA কোর্সে দেখানো হয়েছে)।

২ · DP রিকারেন্স

$c[i][j]$ সংজ্ঞায়িত করি $X$-এর প্রথম $i$ ক্যারেক্টার ($x_1 \ldots x_i$) ও $Y$-এর প্রথম $j$ ক্যারেক্টার ($y_1 \ldots y_j$)-এর LCS দৈর্ঘ্য হিসেবে।

$$ c[i][j] = \begin{cases} 0 & i = 0 \text{ অথবা } j = 0 \\ c[i-1][j-1] + 1 & i, j > 0 \text{ এবং } x_i = y_j \\ \max\big(c[i-1][j],\, c[i][j-1]\big) & i, j > 0 \text{ এবং } x_i \ne y_j \end{cases} $$

অপটিমাল সাবস্ট্রাকচার প্রমাণ (কেস-বাই-কেস):

দুই ক্ষেত্রেই বড় সমস্যার অপটিমাল উত্তর ছোট সাবপ্রবলেমের অপটিমাল উত্তর থেকে সরাসরি গঠিত হচ্ছে — এটাই অপটিমাল সাবস্ট্রাকচার। আর $c[i-1][j]$-এর মতো একই অবস্থা $c[i][j]$ ও $c[i-1][j+1]$ উভয়ের গণনায় আসতে পারে — এটাই ওভারল্যাপিং সাবপ্রবলেম, যেমনটি L24-এ সাধারণভাবে ব্যাখ্যা করা হয়েছে।

৩ · যাচাই — নেইভ এক্সপোনেনশিয়াল রিকার্সন বনাম DP

উপরের রিকারেন্সটি cache ছাড়া সরাসরি রিকার্সিভভাবে লিখলে এটি $O(2^{m+n})$ সময়ে চলে (প্রতিটি অমিলে দুটি শাখা তৈরি হয়) — একটি ধীর কিন্তু নিঃসন্দেহে সঠিক গ্রাউন্ড ট্রুথ। নিচের কোডে এটি এবং ট্যাবুলেটেড DP পাশাপাশি চালিয়ে একাধিক ছোট র‍্যান্ডম স্ট্রিং জোড়ায় (দৈর্ঘ্য $\le 9$, শুধু 'a'/'b' অক্ষর ব্যবহার করে যাতে মিল ঘন ঘন হয়) তুলনা করা হয়েছে।

import random

def lcs_brute(X, Y, i, j):
    # নেইভ এক্সপোনেনশিয়াল রিকার্সন -- কোনো cache নেই
    if i == 0 or j == 0:
        return 0
    if X[i - 1] == Y[j - 1]:
        return 1 + lcs_brute(X, Y, i - 1, j - 1)
    return max(lcs_brute(X, Y, i - 1, j), lcs_brute(X, Y, i, j - 1))

def lcs_dp(X, Y):
    # ট্যাবুলেটেড DP -- ঠিক একই রিকারেন্স, ইটারেটিভভাবে
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

rng = random.Random(7)
alphabet = "ab"
print(f"{'X':>10} | {'Y':>10} | {'brute':>5} | {'dp':>3}")
for trial in range(10):
    lx = rng.randint(1, 9)
    ly = rng.randint(1, 9)
    X = "".join(rng.choice(alphabet) for _ in range(lx))
    Y = "".join(rng.choice(alphabet) for _ in range(ly))
    b = lcs_brute(X, Y, len(X), len(Y))
    d = lcs_dp(X, Y)
    assert b == d, "মিসম্যাচ!"
    print(f"{X:>10} | {Y:>10} | {b:>5} | {d:>3}")

print("\nক্লাসিক টেক্সটবুক উদাহরণ:")
X, Y = "ABCBDAB", "BDCABA"
print(X, Y, "-> LCS দৈর্ঘ্য:", lcs_dp(X, Y), "(brute:", lcs_brute(X, Y, len(X), len(Y)), ")")