ডায়নামিক প্রোগ্রামিং৭ মিনিট পড়া

লংগেস্ট কমন সাবসিকোয়েন্স বা দীর্ঘতম সাধারণ উপক্রম (Longest Common Subsequence)

দুটি সিকোয়েন্সের বা অনুক্রমের মধ্যে থাকা দীর্ঘতম একই অংশ বা গল্পটি খুঁজে বের করুন — যেখানে মাঝখানের কিছু অংশ এড়িয়ে যাওয়া বা স্কিপ (skip) করা সম্ভব
time:\(O(m \cdot n)\)space:\(O(m \cdot n)\) বা \(O(\min(m,n))\)

ধরুন, দুই বন্ধু গ্রীষ্মের ছুটিতে তাদের দৈনন্দিন কাজকর্ম ডায়েরিতে লিখে রাখত। তাদের ডায়েরির লেখা হয়তো একদম শব্দে-শব্দে (word-for-word) হুবহু মিলবে না, কিন্তু এর মাঝেও একটি সাধারণ জিনিসের বা লেখার মিল থাকবে — আর তা হলো তাদের দু'জনে মিলে কাটানো কিছু মুহূর্তের ঘটনা, যা তারা হয়তো অন্য কোনো ঘটনার মাঝে মাঝে লিখে রাখলেও, মূলত একই ক্রমে (same order) তা লিখে রেখেছে। ঠিক এভাবেই, তাদের এই শেয়ার করা বা দু'জনের জীবনের থাকা দীর্ঘতম সাধারণ গল্প বা ঘটনাটি (shared storyline) খুঁজে বের করাই হলো লংগেস্ট কমন সাবসিকোয়েন্স বা দীর্ঘতম সাধারণ উপক্রম (Longest Common Subsequence — LCS) সমস্যার মূল কাজ।

একটি সাবসিকোয়েন্স বা উপক্রম (subsequence)-এ মূলত তার ইলিমেন্টগুলোর বা উপাদানের রিলেটিভ অর্ডার (relative order) বা পুরোনো ক্রমগুলো হুবহু ধরে রাখা হয়, তবে এর মাঝখানের কিছু উপাদান বা এলিমেন্টকে অনায়াসে স্কিপ (skip) বা এড়িয়ে যাওয়া যায়। তাই 'ACE' হলো মূলত 'ABCDE'-এর একটি সাবসিকোয়েন্স — যেখানে আপনি সহজেই B এবং D-কে স্কিপ বা এড়িয়ে যেতে পারেন। তবে একটি সাবস্ট্রিং-কে (substring) অবশ্যই কন্টিগুয়াস বা সংলগ্ন (contiguous) বা পাশাপাশি হতে হবে — যেমন 'BCD' হলো একটি সাবস্ট্রিং, তবে 'ACE' মোটেও কোনো সাবস্ট্রিং নয়। LCS-এর কাজ হলো মূলত এই দুইটি (both) স্ট্রিংয়ের (strings) মধ্যেই থাকা দীর্ঘতম বা লম্বা সাবসিকোয়েন্সটিকে (subsequence) খুঁজে বের করা।

2D ডিপি (DP) টেবিল বা ছক

ধরি dp[i][j] = s স্ট্রিংয়ের প্রথম i সংখ্যক অক্ষর এবং t স্ট্রিংয়ের প্রথম j সংখ্যক অক্ষরের (characters) মধ্যকার LCS-এর দৈর্ঘ্যকে বোঝায়। আর এদের টেবিল বা ছকটি মূলত (m+1) × (n+1) সাইজের বা আকারের হয়ে থাকে — যেখানে এর "এম্পটি প্রিফিক্স বা ফাঁকা প্রিফিক্স (empty prefix)" বা বেস কেসগুলোর (base cases) জন্য একটি অতিরিক্ত সারি (row) এবং কলাম (column) থাকে: dp[0][j] = 0 এবং dp[i][0] = 0 (কারণ একটি এম্পটি বা খালি (empty) স্ট্রিংয়ের সাথে এর LCS-এর মান সবসময়ই 0 হয়ে থাকে)।

রিকারেন্স বা ট্রানজিশন (The Recurrence)

প্রতিটি সেলের বা ঘরের (i, j) জন্য:

যদি s[i-1] == t[j-1] হয় (অর্থাৎ দুটির ক্যারেক্টার বা অক্ষর যদি একে অপরের সাথে মিলে যায় বা ম্যাচ করে): dp[i][j] = dp[i-1][j-1] + 1। অর্থাৎ আমরা এই মিলে যাওয়া বা ম্যাচ করা ক্যারেক্টারটির সাহায্যে দুটি ছোট প্রিফিক্সের (prefixes) LCS-কে আরও এক ধাপ বাড়িয়ে দিই।

আর যদি ক্যারেক্টার বা অক্ষরগুলি না মিলে: dp[i][j] = max(dp[i-1][j], dp[i][j-1])। এক্ষেত্রে আমরা s-এর শেষ ক্যারেক্টারটিকে অথবা t-এর শেষ ক্যারেক্টারটিকে (character) ইগনোর বা উপেক্ষা (ignoring) করার মাধ্যমে মূলত সেরা বা সবচেয়ে ভালো মানের LCS-টি গ্রহণ করি।

এর চূড়ান্ত বা ফাইনাল উত্তরটি হলো: dp[m][n]।

আসল বা মূল সিকোয়েন্সটিকে বা অনুক্রমটিকে পুনরায় খুঁজে বের করা বা ট্রেস-ব্যাক (Trace-back) করা

এই টেবিলটি আপনাকে শুধু এর দৈর্ঘ্য বা লেন্থের (length) পরিমাণটি বলে। তবে আসল LCS-টিকে বের করার জন্য, আপনাকে dp[m][n] থেকে পেছনের দিকে সরে আসতে হবে বা ট্রেস ব্যাক (trace back) করতে হবে: যদি s[i-1] == t[j-1] হয়, তবে ধরে নিবেন যে এই ক্যারেক্টারটি (character) বর্তমান LCS-এর মধ্যে রয়েছে — তখন এটিকে রেকর্ড বা সেভ করুন এবং ডায়াগোনালি বা তির্যকভাবে (i-1, j-1) এর দিকে সরে যান। অন্যথায়, আপনার সবচেয়ে বড় বা বৃহত্তর প্রতিবেশীর (neighbor) দিকে (ডানে বা বামে (up or left)) সরে যান। এই ডায়াগোনাল মুভ বা তির্যকভাবে চলাকালীন সময়ে ক্যারেক্টারগুলোকে (characters) বা মানগুলোকে সংগ্রহ করুন (এবং সবশেষে তাদের এই সাজানোর ক্রমটকে রিভার্স বা উল্টে (reverse) দিন)।

স্পেস বা জায়গাকে অপ্টিমাইজ (Optimize) করা বা কমানো

এই dp[i][j]-টি মূলত শুধুমাত্র dp[i-1][j], dp[i-1][j-1], এবং dp[i][j-1]-এর মানের ওপরেই নির্ভর করে — অর্থাৎ শুধু এর ঠিক আগের সারিটি আর একটি অতিরিক্ত ভেরিয়েবল বা চলকের (variable) উপর। এক্ষেত্রে আপনি চাইলে শুধু দুটি সারি বা রো (rows) রেখে এর স্পেস বা মেমরিকে কমিয়ে অনায়াসে \(O(\min(m,n))\)-এ নামিয়ে আনতে পারেন। এর ট্রেডঅফ (tradeoff) বা খারাপ দিকটি হলো: এর ফলে আপনি আপনার আসল সিকোয়েন্সটিকে বা অনুক্রমটিকে পুনরায় ট্রেস-ব্যাক (trace back) করে খুঁজে বের করার ক্ষমতা হারাবেন।

দ্রষ্টব্য: মূলত ইউনিক্সের (Unix) 'diff' কমান্ডটির পেছনের মূল ইঞ্জিনটি হলো এই LCS অ্যালগরিদমটি — তবে এটি একক বা ইন্ডিভিজুয়াল অক্ষরের (individual characters) পরিবর্তে মূলত পাঠ্য বা টেক্সট লাইনের (lines of text) উপর কাজ করে। দুটি ফাইল সাধারণত অনেকগুলো লাইনের সাথে একে ওপরের মিল পেয়ে থাকে; তাই diff কমান্ডটি শুধুমাত্র এ দুটির মাঝে ঠিক কী কী পরিবর্তন হয়েছে সেটিকে হাইলাইট (highlights) করে দেখায়।

LCS — দৈর্ঘ্য (length) এবং রিকনস্ট্রাকশন (reconstruction)

def lcs(s, t):
    m, n = len(s), len(t)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    # reconstruct
    res, i, j = [], m, n
    while i > 0 and j > 0:
        if s[i-1] == t[j-1]:
            res.append(s[i-1]); i -= 1; j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], ''.join(reversed(res))


print(lcs('ABCBDAB', 'BDCAB'))  # (4, 'BCAB') or similar
Output
(4, 'BCAB')

Complexity

⏱️ সময় বা টাইম (Time)
m = s-এর দৈর্ঘ্য, n = t-এর দৈর্ঘ্য; প্রতিটি সেলে বা ঘরে \(O(1)\) পরিমাণ সময় লাগে
m×n টেবিল বা ছক পূরণ করা (Fill m×n table) \(O(m \cdot n)\)
📊 জায়গা বা স্পেস (সম্পূর্ণ বা ফুল টেবিল / full table)
লংগেস্ট কমন সাবসিকোয়েন্স বা দীর্ঘতম সাধারণ উপক্রম (LCS) স্ট্রিংটিকে পুনরায় গঠন বা ট্রেস-ব্যাক (trace back) করতে হলে পুরো টেবিলটি বা ছকটির প্রয়োজন হয়
রিকনস্ট্রাকশন বা পুনর্নির্মাণ করার জন্য (For reconstruction) \(O(m \cdot n)\)
🪄 জায়গা বা স্পেস (শুধুমাত্র দৈর্ঘ্য বা length only)
সবচেয়ে ছোট বা খাটো স্ট্রিংটিকে মূলত কলাম বা column হিসেবে বিবেচনা করুন; একবারে শুধুমাত্র দুটি সারি (rows) মেমরিতে বা ক্যাশে জমা রাখুন
উইটি রো বা সারি (Two rows) \(O(\min(m,n))\)
🔍 রিকনস্ট্রাকশন বা পুনর্নির্মাণ (Reconstruction)
টেবিলটি জুড়ে উপরের দিকে বা বাম দিকে করে সর্বাধিক m+n ধাপে বা ধাপে ধাপে সরে আসা বা সম্পন্ন করা যায়
ট্রেস-ব্যাক (Trace-back) \(O(m+n)\)
🐌 ব্রুট ফোর্স বা সম্পূর্ণ চেষ্টা বা সাধারণ পদ্ধতি (Brute force)
s-এর সমস্ত 2^m সংখ্যক সাবসিকোয়েন্সগুলোকে তৈরি বা জেনারেট (Generate) করুন, এবং সেগুলোর প্রতিটিকে \(O(n)\) সময়ে t-এর সাথে চেক বা যাচাই করে দেখুন
সব সাবসিকোয়েন্স (All subsequences) \(O(n \cdot 2^m)\)

ছোট কুইজ

LCS বা লংগেস্ট কমন সাবসিকোয়েন্স (Longest Common Subsequence)-এর ক্ষেত্রে, 'ABCBDAB' এবং 'BDCAB'-এর দৈর্ঘ্য মূলত 4 সংখ্যক হয়। তাহলে নিচের কোনটি এর মধ্যে একটি সঠিক বা ভ্যালিড (valid) LCS হবে?

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