DP-র ক্লাসিক সমস্যা ২ — LCS, edit distance আর matrix chain

১ · দুটি sequence মেলানো — diff, DNA আর বানান

পর্ব ৫২-এ (Dynamic programming-এর ভিত্তি) দেখেছেন, dynamic programming কাজ করে যখন দুটি শর্ত থাকে: বড় সমস্যার সেরা উত্তর ছোট সমস্যার সেরা উত্তর দিয়ে গড়া যায় (optimal substructure), আর একই ছোট সমস্যা বারবার ফিরে আসে (overlapping subproblems). পর্ব ৫৩-এ (DP-র ক্লাসিক সমস্যা ১) knapsack, coin change আর LIS-এ সেই ধারণা খাটিয়েছেন — সেখানে ইনপুট ছিল একটি তালিকা। এই পর্বের প্রথম ভাগে ইনপুট দুটি sequence, আর প্রশ্ন: এরা কতটা মেলে? দ্বিতীয় ভাগে আসবে নতুন এক ধাঁচ — interval-এর ওপর DP.

দুটি sequence মেলানোর প্রশ্ন আপনি প্রতিদিনই দেখেন, হয়তো খেয়াল না করে:

• diff আর git: একটি ফাইলের পুরোনো আর নতুন সংস্করণে কোন লাইন বাদ গেছে (−), কোন লাইন নতুন এসেছে (+), আর কোনগুলো একই আছে — git-এর প্রতিটি commit-এর পরিবর্তন এভাবেই দেখানো হয়। “একই আছে” এমন লাইনগুলো দুই ফাইলের একটি সবচেয়ে লম্বা সাধারণ ক্রম।
• DNA তুলনা: DNA হলো A, C, G, T — চারটি অক্ষরের একটি লম্বা স্ট্রিং। দুটি প্রাণীর একই জিন কতটা মেলে, কোথায় অক্ষর বদলেছে, কোথায় বাদ পড়েছে — জীববিজ্ঞানীরা এটিই হিসাব করেন।
• বানান-সংশোধক: ফোনে ইংরেজি অক্ষরে বাংলা লিখছেন (Banglish) — “bhalo” বা “valo” লিখতে গিয়ে ভুলে লিখলেন “bhlo”. কিবোর্ড অ্যাপ বা phonetic টাইপিং সফটওয়্যার অভিধানের কোন শব্দটি আপনার লেখার সবচেয়ে কাছে, তা বের করে পরামর্শ দেয়। “কাছে” মাপার একটি সংখ্যা লাগে।
• নকল ধরা: দুটি অ্যাসাইনমেন্ট বা দুটি প্রোগ্রামের কতটা অংশ একই ক্রমে মেলে, তা দেখে plagiarism-এর সন্দেহ করা হয়।

Subsequence আর substring — একটি জরুরি পার্থক্য

একটি স্ট্রিং থেকে কিছু অক্ষর (শূন্য বা বেশি) বাদ দিয়ে, বাকিগুলোর ক্রম না বদলে যা থাকে, সেটি একটি subsequence. যেমন “GATCA” থেকে A আর C বাদ দিলে “GTA” — এটি subsequence, যদিও G, T, A মূল স্ট্রিংয়ে পাশাপাশি নেই। অন্যদিকে substring মানে পাশাপাশি থাকা একটি টুকরো: “ATC” হলো “GATCA”-র substring, “GTA” নয়। প্রতিটি substring একটি subsequence, কিন্তু উল্টোটা সত্য নয়। n অক্ষরের স্ট্রিংয়ে substring মোটে প্রায় n²/2 টি, কিন্তু subsequence 2ⁿ টি — প্রতিটি অক্ষর রাখা বা না রাখা।

LCS-এর brute force উপায়: প্রথম স্ট্রিং X-এর (দৈর্ঘ্য n) প্রতিটি subsequence নিন, দেখুন সেটি Y-এরও (দৈর্ঘ্য m) subsequence কি না — প্রতিটি যাচাইয়ে দুই pointer দিয়ে O(m) সময় লাগে। মোট O(m · 2ⁿ). n = 50 হলেই 2⁵⁰ ≈ 10¹⁵ — পৃথিবীর দ্রুততম কম্পিউটারেও অবাস্তব। অথচ DP দিয়ে n = m = 5000-এর LCS এক সেকেন্ডেরও কম সময়ে বের হয়। পার্থক্যটা exponential থেকে polynomial — ঠিক পর্ব ৫২-এ Fibonacci-তে যেমন দেখেছেন।

২ · LCS — দুই prefix-এর DP আর তার প্রমাণ

DP-র প্রথম কাজ state ঠিক করা: কোন ছোট প্রশ্নগুলোর উত্তর জানলে বড়টির উত্তর আসবে? দুটি sequence-এর সমস্যায় প্রায় সবসময় উত্তর একই — দুই prefix. এই অংশের গণিতে স্ট্রিং 1-based: X = x₁x₂…x_n, Y = y₁…y_m, আর X_i মানে X-এর প্রথম i টি অক্ষর।

কোনো একটি স্ট্রিং খালি হলে সাধারণ কিছুই নেই: L[0][j] = L[i][0] = 0 — এগুলো base case. এবার শেষ অক্ষর দুটি x_i আর y_j দেখুন। দুটি ঘটনা:

কেন সূত্রটি ঠিক — প্রমাণ

বিশ্ববিদ্যালয় বা চাকরির লিখিত পরীক্ষায় এই প্রমাণটি প্রায়ই চাওয়া হয়। ধরুন Z = z₁…z_k হলো X_i আর Y_j-এর একটি LCS (k = L[i][j]).

• x_i = y_j হলে: প্রথমে দাবি, z_k = x_i. যদি না হতো, তাহলে Z-এর শেষে x_i জুড়ে দিলে দৈর্ঘ্য k + 1-এর একটি সাধারণ subsequence পেতাম (দুই স্ট্রিংয়েই x_i সবার শেষে, Z-এর সব অক্ষরের পরে) — Z সবচেয়ে লম্বা, এই কথার সাথে স্ববিরোধ. তাহলে z₁…z_k−1 হলো X_i−1 আর Y_j−1-এর একটি সাধারণ subsequence. এটিই সবচেয়ে লম্বা: আরও লম্বা কোনো W থাকলে W-এর শেষে x_i জুড়ে দিয়ে Z-এর চেয়ে লম্বা উত্তর পেতাম। তাই L[i][j] = L[i−1][j−1] + 1.
• x_i ≠ y_j হলে: z_k একসাথে x_i আর y_j দুটোই হতে পারে না। z_k ≠ x_i হলে x_i উত্তরে কাজে লাগেনি, তাই Z আসলে X_i−1 আর Y_j-এর সাধারণ subsequence, অর্থাৎ k ≤ L[i−1][j]. একইভাবে z_k ≠ y_j হলে k ≤ L[i][j−1]. আর উল্টো দিকে, ছোট prefix-এর যেকোনো সাধারণ subsequence বড় prefix-এরও সাধারণ subsequence, তাই k ≥ দুটোর max. দুই দিক মিলে k = max(L[i−1][j], L[i][j−1]).

এই যুক্তির ধরনকে বলে cut-and-paste: “উপ-সমস্যার উত্তর সেরা না হলে, সেটি কেটে সেরাটি বসিয়ে বড় উত্তরকেও ভালো করা যেত” — পর্ব ৫২-এর optimal substructure-এর প্রমাণের সাধারণ কৌশল। একই যুক্তি এই পর্বের প্রতিটি সমস্যায় খাটবে।

কেন memo বা টেবিল লাগে

সূত্রটি সরাসরি recursion হিসেবে লিখলে, অক্ষর না মিললে প্রতিটি ডাক দুটি নতুন ডাক দেয়, আর গভীরতা n + m পর্যন্ত — worst case-এ প্রায় 2^n+m ডাক। কিন্তু ভিন্ন ভিন্ন প্রশ্ন (i, j) আছে মাত্র (n + 1)(m + 1) টি; L(i−1, j−1) প্রশ্নটি L(i−1, j) আর L(i, j−1) দুই দিক থেকেই আসে। তাই হয় memoization (প্রতিটি (i, j)-এর উত্তর একবার হিসাব করে রেখে দেওয়া), নয়তো tabulation — নিচ থেকে টেবিল ভরা। এখানে tabulation সহজ: প্রতিটি ঘর নির্ভর করে শুধু তার ওপরের, বাঁয়ের আর ওপর-বাঁয়ের ঘরের ওপর, তাই সারি ধরে বাঁ থেকে ডানে ভরলেই প্রতিটি ঘরের দরকারি মান আগে থেকে তৈরি থাকে।

Pseudocode — LCS length (strings 1-based: x[1..n], y[1..m])

for i = 0..n:  L[i][0] = 0
for j = 0..m:  L[0][j] = 0
for i = 1..n:
    for j = 1..m:
        if x[i] == y[j]:  L[i][j] = L[i-1][j-1] + 1          // diagonal  ↖
        else if L[i-1][j] >= L[i][j-1]:  L[i][j] = L[i-1][j]  // up        ↑
        else:  L[i][j] = L[i][j-1]                          // left      ←
return L[n][m]

প্রতিটি ঘরে তীর-চিহ্ন (↖, ↑, ←) মনে রাখার মানে, মানটি কোন দিক থেকে এসেছে। উত্তর ফিরে পেতে এই তীরগুলোই কাজে লাগবে। আর লক্ষ করুন ওপর আর বাঁ সমান হলে আমরা ↑ নিচ্ছি — একটি নির্দিষ্ট নিয়ম, যাতে হাতে করা trace আর কোডের আউটপুট একই হয়।

৩ · LCS-এর টেবিল হাতে ভরা আর উত্তর ফিরে পাওয়া

দুটি ছোট DNA টুকরো নিন: X = GATCA (সারি, i), Y = GCTA (কলাম, j). খালি prefix-কে ε দিয়ে দেখানো হলো। প্রতিটি ঘরে তীর আর মান; “·” মানে এখনো ভরা হয়নি।

পুনর্গঠন — দৈর্ঘ্য থেকে আসল sequence

টেবিল শুধু দৈর্ঘ্য দেয়। আসল LCS পেতে কোণ (n, m) থেকে শুরু করে তীর ধরে পেছনে হাঁটুন: ↖ হলে অক্ষরটি উত্তরে যোগ করে কোণাকুণি সরুন, ↑ হলে ওপরে, ← হলে বাঁয়ে। প্রতি ধাপে i বা j (বা দুটোই) এক কমে, তাই এই reconstruction O(n + m) সময় নেয়। তীর আলাদা করে রাখারও দরকার নেই — প্রতিটি ঘরে দাঁড়িয়ে আবার তুলনা করলেই বোঝা যায় মান কোথা থেকে এসেছে।

একটি সূক্ষ্ম কথা: LCS একটিই হবে, এমন নয়। এখানে “GCA”-ও একটি LCS — G, C, A দুই স্ট্রিংয়েই এই ক্রমে আছে। আমরা সমান হলে ↑ বেছেছি বলে GTA এসেছে; সমান হলে ← বাছলে GCA আসত। দুটোই সঠিক। পরীক্ষায় “একটি LCS লিখুন” বললে যেকোনো একটি চলে, কিন্তু কোড আর হাতের trace মেলাতে চাইলে একই নিয়ম মানতে হবে। সব ভিন্ন LCS তালিকা করতে চাইলে সেগুলোর সংখ্যা নিজেই exponential হতে পারে।

পেছনে হাঁটার সময় যা পাওয়া যায় তা আসলে একটি পূর্ণ diff: ↖ মানে দুই দিকেই আছে (অপরিবর্তিত), ↑ মানে শুধু X-এ আছে (“−”, মুছে ফেলা), ← মানে শুধু Y-এ (“+”, নতুন যোগ)। আমাদের উদাহরণে diff দাঁড়ায় G +C −A T −C A — অর্থাৎ GATCA থেকে A আর C মুছে আর একটি C যোগ করে GCTA. git ঠিক এভাবেই, অক্ষরের বদলে পুরো লাইন ধরে, পরিবর্তন দেখায় (যদিও তার অ্যালগরিদম আরও চতুর — ভাবনার প্রশ্ন ১ দেখুন)।

খরচ, আর দুই সারির কৌশল

(n + 1)(m + 1) টি ঘর, প্রতিটিতে একটি তুলনা আর একটি max — সময় Θ(nm), পুরো টেবিল রাখলে জায়গা Θ(nm). n = m = 10⁴ হলে 10⁸ ঘর: C++-এ সময় এক সেকেন্ডের কাছাকাছি, কিন্তু int-এর টেবিলে প্রায় 400 MB মেমরি — সাধারণ কনটেস্টের 256 MB সীমা পেরিয়ে যায়। অথচ সারি i ভরতে লাগে শুধু সারি i − 1. তাই শুধু দৈর্ঘ্য চাইলে দুটি সারি রাখুন (rolling array), আর ছোট স্ট্রিংটিকে কলাম বানান: জায়গা O(min(n, m)). এটি time–space trade-off নয় — সময় একই থাকে, শুধু জায়গা কমে।

// LCS length in O(min(n, m)) extra space: keep only the previous row
int lcsLength(const string& a, const string& b) {   // pass the shorter string as b
    vector<int> prev(b.size() + 1, 0), cur(b.size() + 1, 0);
    for (char c : a) {
        for (size_t j = 1; j <= b.size(); ++j)
            cur[j] = (c == b[j-1]) ? prev[j-1] + 1 : max(prev[j], cur[j-1]);
        swap(prev, cur);                                // cur[0] stays 0 for every row
    }
    return prev[b.size()];
}

কিন্তু দুই সারি রাখলে তীরগুলো হারিয়ে যায় — আসল LCS আর ফিরে পাওয়া যায় না। ১৯৭৫ সালে Daniel Hirschberg এর একটি সুন্দর সমাধান দেন: প্রথম স্ট্রিংটিকে মাঝখানে ভাগ করুন, ওপরের অর্ধেকের জন্য সামনে থেকে আর নিচের অর্ধেকের জন্য পেছন থেকে দুই সারির DP চালান, আর দেখুন দ্বিতীয় স্ট্রিংয়ের কোন বিন্দুতে ভাগ করলে দুই অর্ধেকের যোগফল সবচেয়ে বড়। তারপর দুই ভাগে divide and conquer (পর্ব ৪৯) চালান। Hirschberg-এর অ্যালগরিদম মোট O(nm) সময়েই (প্রতি স্তরে কাজ অর্ধেক হয়, তাই মোট প্রায় 2nm) আর O(n + m) জায়গায় পুরো LCS দেয়। লম্বা DNA-র alignment-এ এই কৌশল এখনো ব্যবহৃত হয়।

৪ · Edit distance — insert, delete আর replace

ধরুন একটি Banglish কিবোর্ডের অভিধানে আছে “valo”, আর ব্যবহারকারী লিখলেন “bhalo”. কোন শব্দ পরামর্শ দেবেন, তা ঠিক করতে দরকার একটি দূরত্ব: সবচেয়ে কম কয়টি এক-অক্ষরের পরিবর্তনে একটি শব্দ আরেকটি হয়? পরিবর্তন তিন রকম — একটি অক্ষর যোগ (insert), মুছে ফেলা (delete), বা অন্য অক্ষরে বদলে দেওয়া (replace), প্রতিটির খরচ 1. এই সংখ্যার নাম edit distance, আর সোভিয়েত গণিতবিদ Vladimir Levenshtein-এর নামে একে Levenshtein distance-ও বলে। “bhalo” থেকে “valo”: b মুছে দিন, h-কে v বানান — ২টি ধাপ। একটিতে কি সম্ভব? না: দৈর্ঘ্যই আলাদা (৫ আর ৪), তাই অন্তত একটি delete লাগবে, আর শুধু একটি অক্ষর মুছে “bhalo” থেকে “valo” হয় না।

State আর সূত্র

LCS-এর মতোই দুই prefix: D[i][j] = a-এর প্রথম i টি অক্ষরকে b-এর প্রথম j টি অক্ষরে বদলানোর সবচেয়ে কম খরচ। base case এবার 0 নয়: খালি স্ট্রিং থেকে j অক্ষরের স্ট্রিং বানাতে j টি insert, তাই D[0][j] = j; i অক্ষরকে খালি করতে i টি delete, তাই D[i][0] = i.

এখানে [a_i ≠ b_j] মানে অক্ষর আলাদা হলে 1, একই হলে 0. যুক্তিটি সবচেয়ে ভালো বোঝা যায় দুই শব্দকে একটির নিচে আরেকটি সাজিয়ে — একটি alignment. সেরা সাজানোর একেবারে শেষ কলামটি তিনটির একটি হতেই হবে: (১) a_i-এর নিচে ফাঁকা — a_i মুছে ফেলা হয়েছে, বাকি খরচ D[i−1][j]; (২) b_j-এর ওপরে ফাঁকা — b_j যোগ হয়েছে, বাকি D[i][j−1]; (৩) a_i-এর নিচে b_j — মিললে খরচ 0, না মিললে একটি replace. শেষ কলাম বাদ দিলে যা থাকে তা ছোট prefix-দুটির একটি alignment, আর cut-and-paste যুক্তিতে সেটিকেও সেরা হতে হবে। তিনটির মধ্যে সবচেয়ে কমটিই উত্তর। ∎

এখানেও একাধিক সমান-ভালো উত্তর আছে: “replace b → v, তারপর delete h”-ও ২টি ধাপ। কোন সমান বিকল্প আগে যাচাই করা হবে, তার ওপর নির্ভর করে কোনটি ছাপা হবে। সময় Θ(nm); শুধু দূরত্ব চাইলে LCS-এর মতোই দুই সারি, জায়গা O(min(n, m)); অপারেশনের তালিকা চাইলে পুরো টেবিল বা Hirschberg-এর কৌশল।

LCS-এর সাথে সম্পর্ক, আর বাস্তবের রূপভেদ

• শুধু insert আর delete চললে: replace নিষেধ হলে দূরত্ব = n + m − 2 · LCS. কারণ LCS-এর অক্ষরগুলো রেখে বাকি সব a থেকে মুছে, b-এর বাকিগুলো যোগ করতে হয়। “bhalo” আর “valo”-র LCS “alo” (3), তাই 5 + 4 − 6 = 3 — replace থাকলে যা 2. diff ঠিক এই মডেলটি ব্যবহার করে: লাইন হয় মোছা হয়, নয়তো যোগ হয়, “বদলানো” লাইন আসলে একটি − আর একটি +.
• Transposition: টাইপ করার সময় পাশাপাশি দুটি অক্ষর উল্টে যাওয়া (“teh” লিখতে চেয়েছিলেন “the”) খুব সাধারণ। Levenshtein-এ এর খরচ 2, অথচ মানুষের চোখে একটিই ভুল। ১৯৬৪ সালে Frederick Damerau দেখান, বানান-ভুলের বেশিরভাগই একটিমাত্র insert, delete, replace বা পাশাপাশি দুটি অক্ষরের অদলবদল। সূত্রে একটি চতুর্থ বিকল্প যোগ করলে — a_i = b_j−1 আর a_i−1 = b_j হলে D[i−2][j−2] + 1 — পাওয়া যায় Damerau-Levenshtein-এর একটি প্রচলিত রূপ (একে optimal string alignment distance-ও বলে)। খরচ একই Θ(nm).
• ভিন্ন ভিন্ন খরচ: কিবোর্ডে পাশাপাশি থাকা অক্ষরের replace (যেমন Banglish-এ b আর v, s আর sh-এর গোলমাল) কম খরচের ধরা যায়। সূত্রে “+ 1”-এর জায়গায় শুধু একটি খরচের টেবিল বসে; DP একই থাকে।

৫ · কোডে — LCS-এর diff আর edit distance-এর অপারেশন

এবার দুটি অ্যালগরিদম একসাথে, পুনর্গঠনসহ। lcsDiff LCS আর diff (− মানে শুধু প্রথমটিতে, + মানে শুধু দ্বিতীয়টিতে) ছাপে; edit দূরত্ব আর অপারেশনের তালিকা। ইনপুট: ওপরের দুই ডায়াগ্রামের স্ট্রিং, পাঠ্যবইয়ের পরিচিত ABCBDAB/BDCABA, আর একটি লম্বা Banglish শব্দ। কোডে স্ট্রিং 0-based, তাই টেবিলের i-তম সারির অক্ষর a[i-1].

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using Table = vector<vector<int>>;
void lcsDiff(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    Table L(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            L[i][j] = a[i-1] == b[j-1] ? L[i-1][j-1] + 1 : max(L[i-1][j], L[i][j-1]);
    vector<string> out; string common;            // walk back from the corner L[n][m]
    for (int i = n, j = m; i > 0 || j > 0; )
        if (i && j && a[i-1] == b[j-1]) { common += a[i-1]; out.push_back(string(1, a[--i])); --j; }
        else if (i && (!j || L[i-1][j] >= L[i][j-1])) out.push_back("-" + string(1, a[--i]));
        else out.push_back("+" + string(1, b[--j]));
    reverse(common.begin(), common.end());
    cout << "LCS(" << a << ", " << b << ") = " << common << ", length " << L[n][m] << "\n  diff:";
    for (auto it = out.rbegin(); it != out.rend(); ++it) cout << ' ' << *it;
    cout << '\n';
}
void edit(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    Table D(n + 1, vector<int>(m + 1));
    for (int i = 0; i <= n; ++i) for (int j = 0; j <= m; ++j)
        D[i][j] = (i == 0 || j == 0) ? i + j
                : min({D[i-1][j] + 1, D[i][j-1] + 1, D[i-1][j-1] + (a[i-1] != b[j-1])});
    vector<string> ops;
    for (int i = n, j = m; i > 0 || j > 0; )
        if (i && j && D[i][j] == D[i-1][j-1] + (a[i-1] != b[j-1])) {
            if (a[i-1] != b[j-1]) ops.push_back(string("replace ") + a[i-1] + " by " + b[j-1]);
            --i; --j;
        } else if (i && D[i][j] == D[i-1][j] + 1) ops.push_back(string("delete ") + a[--i]);
        else ops.push_back(string("insert ") + b[--j]);
    cout << "edit(" << a << ", " << b << ") = " << D[n][m] << "\n  ops:";
    for (size_t k = ops.size(); k-- > 0; ) cout << (k + 1 == ops.size() ? " " : ", ") << ops[k];
    cout << '\n';
}
int main() {
    lcsDiff("GATCA", "GCTA");  lcsDiff("ABCBDAB", "BDCABA");
    edit("bhalo", "valo");     edit("bhalobasa", "valobasha");
}

LCS(GATCA, GCTA) = GTA, length 3
  diff: G +C -A T -C A
LCS(ABCBDAB, BDCABA) = BCBA, length 4
  diff: -A B +D C +A B -D A -B
edit(bhalo, valo) = 2
  ops: delete b, replace h by v
edit(bhalobasa, valobasha) = 3
  ops: delete b, replace h by v, insert h

def lcs_diff(a, b):
    n, m = len(a), len(b)
    L = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            L[i][j] = L[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(L[i-1][j], L[i][j-1])
    out, i, j = [], n, m                       # walk back from the corner L[n][m]
    while i > 0 or j > 0:
        if i and j and a[i-1] == b[j-1]:
            out.append(a[i-1]); i -= 1; j -= 1           # diagonal: common letter
        elif i and (not j or L[i-1][j] >= L[i][j-1]):
            out.append("-" + a[i-1]); i -= 1             # up: only in a
        else:
            out.append("+" + b[j-1]); j -= 1             # left: only in b
    out.reverse()
    common = "".join(x for x in out if len(x) == 1)
    print(f"LCS({a}, {b}) = {common}, length {L[n][m]}\n  diff:", *out)

def edit(a, b):
    n, m = len(a), len(b)
    D = [[i + j if i == 0 or j == 0 else 0 for j in range(m + 1)] for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            D[i][j] = min(D[i-1][j] + 1, D[i][j-1] + 1, D[i-1][j-1] + (a[i-1] != b[j-1]))
    ops, i, j = [], n, m
    while i > 0 or j > 0:
        if i and j and D[i][j] == D[i-1][j-1] + (a[i-1] != b[j-1]):
            if a[i-1] != b[j-1]:
                ops.append(f"replace {a[i-1]} by {b[j-1]}")
            i -= 1; j -= 1
        elif i and D[i][j] == D[i-1][j] + 1:
            ops.append(f"delete {a[i-1]}"); i -= 1
        else:
            ops.append(f"insert {b[j-1]}"); j -= 1
    print(f"edit({a}, {b}) = {D[n][m]}\n  ops:", ", ".join(reversed(ops)))

for x, y in [("GATCA", "GCTA"), ("ABCBDAB", "BDCABA")]:
    lcs_diff(x, y)
for x, y in [("bhalo", "valo"), ("bhalobasa", "valobasha")]:
    edit(x, y)

LCS(GATCA, GCTA) = GTA, length 3
  diff: G +C -A T -C A
LCS(ABCBDAB, BDCABA) = BCBA, length 4
  diff: -A B +D C +A B -D A -B
edit(bhalo, valo) = 2
  ops: delete b, replace h by v
edit(bhalobasa, valobasha) = 3
  ops: delete b, replace h by v, insert h

৬ · একই ছাঁচের আত্মীয় — common substring, palindrome আর alignment

Longest common substring — “না মিললে শূন্য”

এবার শর্ত কড়া: সাধারণ অংশটি দুই স্ট্রিংয়েই পাশাপাশি থাকতে হবে। State একটু বদলান: C[i][j] = এমন সবচেয়ে লম্বা সাধারণ অংশ, যা ঠিক a_i আর b_j-এ শেষ হয় (অর্থাৎ দুই prefix-এর শেষে থাকা সবচেয়ে লম্বা সাধারণ অংশ)। অক্ষর মিললে C[i][j] = C[i−1][j−1] + 1, না মিললে 0 — কারণ পাশাপাশির শিকল সেখানেই ভেঙে গেল। উত্তর টেবিলের কোণে নয়, সব ঘরের সর্বোচ্চ মানে।

Pseudocode — longest common substring (1-based)
best = 0
for i = 1..n:  for j = 1..m:
    C[i][j] = (a[i] == b[j]) ? C[i-1][j-1] + 1 : 0
    best = max(best, C[i][j])          // the substring ends at a[i]: a[i-best+1 .. i]

“bhalobasa” আর “valobasha”: LCS হলো “alobasa” (৭), কিন্তু longest common substring “alobas” (৬) — কারণ দ্বিতীয়টিতে s আর শেষ a-র মাঝে h বসে শিকল ভেঙেছে। আর GATCA বনাম GCTA-য় LCS 3 হলেও সাধারণ substring সবচেয়ে লম্বা মাত্র 1 অক্ষরের। সময় Θ(nm); তবে এই সমস্যার দ্রুততর উপায়ও আছে — suffix array বা suffix automaton দিয়ে প্রায় O(n + m) (পর্ব ৫৯)।

Longest palindromic subsequence = LCS(s, উল্টো s)

Palindrome সামনে-পেছনে একই পড়া যায়, যেমন “madam” বা “BABCBAB”. একটি স্ট্রিংয়ের সবচেয়ে লম্বা palindromic subsequence (LPS) খোঁজার সবচেয়ে সুন্দর কৌশল: s আর তার উল্টোর LCS নিন। কেন? s-এর যেকোনো palindromic subsequence উল্টো s-এও একই ক্রমে আছে, তাই দুটির সাধারণ subsequence — অর্থাৎ LPS ≤ LCS. উল্টো দিকটি একটু সূক্ষ্ম: যেকোনো LCS নিজে palindrome না-ও হতে পারে, কিন্তু প্রমাণ করা যায় যে সবসময় অন্তত একটি LCS palindrome হয় (প্রমাণটি একটু সূক্ষ্ম), তাই LCS ≤ LPS. উদাহরণ: s = BBABCBCAB, উল্টো BACBCBABB — LCS 7, আর একটি LPS হলো BABCBAB.

একই সমস্যা সরাসরি interval-এর ওপরও লেখা যায় — যা এই পর্বের দ্বিতীয় ভাগের সেতু: P[i][j] = s_i…s_j-এর LPS; দুই প্রান্তের অক্ষর সমান হলে P[i+1][j−1] + 2, নইলে max(P[i+1][j], P[i][j−1]); P[i][i] = 1. আর একটি পরিচিত প্রশ্নের উত্তর এখান থেকেই আসে: স্ট্রিংটিকে palindrome বানাতে সবচেয়ে কম কয়টি অক্ষর insert করতে হবে? উত্তর n − LPS.

Sequence alignment — জীববিজ্ঞানের DP

১৯৭০ সালে Saul Needleman আর Christian Wunsch প্রোটিনের অ্যামিনো অ্যাসিডের ক্রম তুলনা করতে ঠিক এই ধরনের টেবিল ব্যবহার করেন — যা এখন Needleman–Wunsch অ্যালগরিদম. পার্থক্য শুধু খরচে: “কম খরচ” নয়, “বেশি স্কোর” — মিল হলে পুরস্কার, অমিল বা ফাঁকা (gap) হলে শাস্তি। ধরুন মিল +1, অমিল −1, gap −1. তাহলে S[i][j] = max(S[i−1][j−1] ± 1, S[i−1][j] − 1, S[i][j−1] − 1), বর্ডারে S[i][0] = −i, S[0][j] = −j. GATCA আর GCTA-র সেরা alignment-এর স্কোর 1:

G A T C A
G C T - A
+ - + - +      score = 3 matches - 1 mismatch - 1 gap = 1

লক্ষ করুন, edit distance আসলে এরই একটি বিশেষ রূপ (মিল 0, অমিল আর gap −1, তারপর চিহ্ন উল্টে নেওয়া)। জীববিজ্ঞানে অমিলের শাস্তি অক্ষরের জোড়ার ওপর নির্ভর করে (কোন অ্যামিনো অ্যাসিড কোনটিতে সহজে বদলায় — PAM বা BLOSUM টেবিল), আর একটি লম্বা gap অনেকগুলো আলাদা ছোট gap-এর চেয়ে কম শাস্তি পায় (affine gap). ১৯৮১ সালে Temple Smith আর Michael Waterman দেখান কীভাবে পুরো স্ট্রিং নয়, সবচেয়ে ভালো মেলা টুকরো খোঁজা যায় (local alignment): সূত্রে চতুর্থ বিকল্প 0 যোগ করুন, আর উত্তর নিন সব ঘরের সর্বোচ্চ থেকে — ঠিক longest common substring-এর মতো।

৭ · Interval DP — matrix chain multiplication

এ পর্যন্ত state ছিল দুটি prefix. এবার নতুন ধাঁচ: একটিই sequence, আর state হলো তার একটি টুকরো — interval [i, j]. এই ধরনের DP-কে বলে interval DP, আর তার সবচেয়ে বিখ্যাত উদাহরণ matrix chain multiplication.

বন্ধনী কেন জরুরি — একটি সংখ্যার উদাহরণ

p × q আকারের একটি matrix-কে q × r আকারের একটি matrix দিয়ে গুণ করলে ফল p × r, আর সাধারণ পদ্ধতিতে লাগে p · q · r টি সংখ্যার গুণ (ফলের p · r টি ঘরের প্রতিটিতে q টি গুণ)। Matrix গুণ associative (সহযোজী): বন্ধনী যেভাবেই বসান, (AB)C = A(BC), ফল একই। কিন্তু খরচ? ধরুন A 10 × 30, B 30 × 5, C 5 × 60:

একই উত্তর, অথচ একটি ক্রমে ৬ গুণ বেশি কাজ! কারণ প্রথম ক্রমে মাঝের ফল ছোট (10 × 5), দ্বিতীয়টিতে বড় (30 × 60). প্রশ্ন: n টি matrix A₁A₂…A_n, যেখানে A_i-এর আকার p_i−1 × p_i, তাদের কোন বন্ধনীতে গুণ করলে মোট গুণের সংখ্যা সবচেয়ে কম? (আমরা ক্রম বদলাচ্ছি না — matrix গুণ commutative নয় — শুধু বন্ধনী।) সব বন্ধনী চেষ্টা করা অসম্ভব: n টি matrix-এর বন্ধনীর সংখ্যা Catalan number C_n−1, যা প্রায় 4ⁿ/n^1.5 হারে বাড়ে — n = 20-এ প্রায় ১৭৭ কোটি।

State: শেষ গুণটি কোথায়

A_i…A_j-এর যেকোনো বন্ধনীতে একেবারে শেষ যে গুণটি হয়, সেটি দুটি টুকরোকে জোড়ে: (A_i…A_k)(A_k+1…A_j), কোনো এক k-এর জন্য, i ≤ k < j. বাঁ টুকরোর ফল p_i−1 × p_k, ডানেরটির p_k × p_j, তাই শেষ গুণের খরচ p_i−1p_kp_j. আর দুই টুকরোর ভেতরের বন্ধনী একে অন্যের ওপর নির্ভর করে না — তাই দুটিকেই আলাদাভাবে সেরা করতে হবে (cut-and-paste: কোনো টুকরো সেরা না হলে সেটি বদলে মোট খরচ কমানো যেত)।

যে k-তে min পাওয়া গেল সেটি লিখে রাখুন s[i][j]-এ — বন্ধনী ফিরে পেতে লাগবে। এবার ভরার ক্রম: m[i][j] নির্ভর করে m[i][k] আর m[k+1][j]-এর ওপর — দুটোই [i, j]-এর চেয়ে ছোট interval. তাই সারি ধরে ভরলে চলবে না (m[1][4] ভরতে m[2][4] লাগে, যা নিচের সারিতে); ভরতে হবে দৈর্ঘ্য ধরে: আগে সব দৈর্ঘ্য-২-এর interval, তারপর ৩, … — টেবিলে এটি কর্ণ (diagonal) ধরে ধরে এগোনো।

Pseudocode — matrix chain order (matrices 1-based: Ai is p[i-1] x p[i])

for i = 1..n:  m[i][i] = 0
for len = 2..n:                         // interval length = which diagonal
    for i = 1..n-len+1:
        j = i + len - 1;  m[i][j] = INF
        for k = i..j-1:                 // the last multiplication splits after Ak
            cost = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
            if cost < m[i][j]:  m[i][j] = cost;  s[i][j] = k
return m[1][n]

চারটি matrix নিয়ে হাতে চালানো যাক: p = (10, 30, 5, 60, 10), অর্থাৎ A₁ 10 × 30, A₂ 30 × 5, A₃ 5 × 60, A₄ 60 × 10. টেবিলের প্রতিটি ঘরে “খরচ/k” — k হলো সেরা ভাঙার বিন্দু s[i][j].

খরচ — কেন Θ(n³)

Interval আছে প্রায় n²/2 টি, আর দৈর্ঘ্য L-এর interval-এ k-এর L − 1 টি বিকল্প। মোট ভেতরের লুপ চলে Σ_L=2..n (n − L + 1)(L − 1) = (n³ − n)/6 বার — সময় Θ(n³), জায়গা m আর s মিলে Θ(n²). n = 500 হলে প্রায় 2 × 10⁷ ধাপ, চোখের পলকে। পুনর্গঠন recursion-এ, প্রতিটি s[i][j] একবার পড়ে — O(n).

৮ · Matrix chain কোডে, আর interval DP-র অন্য ছাঁচ

কোডটি তিনটি chain চালায়: শুরুর তিন-matrix-এর উদাহরণ, ডায়াগ্রামের চার-matrix, আর পাঠ্যবইয়ে বহুল ব্যবহৃত ছয়-matrix-এর উদাহরণ (p = 30, 35, 15, 5, 10, 20, 25). খরচ বড় হতে পারে বলে C++-এ long long.

#include <climits>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using Table = vector<vector<long long>>;

string paren(const Table& s, int i, int j) {     // rebuild the brackets from the split table
    if (i == j) return "A" + to_string(i);
    int k = s[i][j];
    return "(" + paren(s, i, k) + paren(s, k + 1, j) + ")";
}
void matrixChain(const vector<long long>& p) {   // matrix Ai has size p[i-1] x p[i], i = 1..n
    int n = p.size() - 1;
    Table m(n + 1, vector<long long>(n + 1, 0)), s = m;
    for (int len = 2; len <= n; ++len)           // shorter chains first
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            m[i][j] = LLONG_MAX;
            for (int k = i; k < j; ++k) {        // last multiplication: (Ai..Ak)(Ak+1..Aj)
                long long cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (cost < m[i][j]) { m[i][j] = cost; s[i][j] = k; }
            }
        }
    cout << "dims";
    for (long long d : p) cout << ' ' << d;
    cout << " -> cost " << m[1][n] << "  order " << paren(s, 1, n) << '\n';
}
int main() {
    matrixChain({10, 30, 5, 60});
    matrixChain({10, 30, 5, 60, 10});
    matrixChain({30, 35, 15, 5, 10, 20, 25});
}

dims 10 30 5 60 -> cost 4500  order ((A1A2)A3)
dims 10 30 5 60 10 -> cost 5000  order ((A1A2)(A3A4))
dims 30 35 15 5 10 20 25 -> cost 15125  order ((A1(A2A3))((A4A5)A6))

def paren(s, i, j):                            # rebuild the brackets from the split table
    if i == j:
        return f"A{i}"
    k = s[i][j]
    return "(" + paren(s, i, k) + paren(s, k + 1, j) + ")"

def matrix_chain(p):                           # matrix Ai has size p[i-1] x p[i], i = 1..n
    n = len(p) - 1
    m = [[0] * (n + 1) for _ in range(n + 1)]
    s = [[0] * (n + 1) for _ in range(n + 1)]
    for length in range(2, n + 1):             # shorter chains first
        for i in range(1, n - length + 2):
            j = i + length - 1
            m[i][j] = None
            for k in range(i, j):              # last multiplication: (Ai..Ak)(Ak+1..Aj)
                cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
                if m[i][j] is None or cost < m[i][j]:
                    m[i][j], s[i][j] = cost, k
    print("dims", *p, "-> cost", m[1][n], " order", paren(s, 1, n))

matrix_chain([10, 30, 5, 60])
matrix_chain([10, 30, 5, 60, 10])
matrix_chain([30, 35, 15, 5, 10, 20, 25])

dims 10 30 5 60 -> cost 4500  order ((A1A2)A3)
dims 10 30 5 60 10 -> cost 5000  order ((A1A2)(A3A4))
dims 30 35 15 5 10 20 25 -> cost 15125  order ((A1(A2A3))((A4A5)A6))

একই ছাঁচ: “interval-এর ভেতরে কোন বিন্দুটি শেষে বা প্রথমে”

Interval DP চেনার লক্ষণ: একটি সারি বা বৃত্ত, পাশাপাশি জিনিস জোড়া লাগানো বা ভাঙা, আর উত্তর নির্ভর করে কোন ক্রমে জোড়া হলো তার ওপর। প্রায় সবসময় state = dp[i][j], আর প্রশ্ন “[i, j]-এর ভেতরে কোন k-কে আলাদা ভূমিকা দেব?”

৯ · AI-এর যুগে DP-র টেবিল — সূচক, বর্ডার আর সমান মান

“LCS-এর কোড দাও” — AI কয়েক সেকেন্ডে লিখবে, আর পাঠ্যবইয়ের উদাহরণে সেটি ঠিক উত্তরও দেবে। DP-র ভুল লুকিয়ে থাকে সূচকে (i না i − 1), বর্ডারে (0 না i), ভরার ক্রমে, আর সমান মানের সময় কোন দিকে যাওয়া হচ্ছে তাতে। আর complexity-র প্রশ্নে AI প্রায়ই আত্মবিশ্বাসী ভুল দাবি করে — যেমন “edit distance-এর অপারেশনসহ উত্তর দুই সারিতেই সম্ভব” বা “matrix chain O(n²)”.

এই পর্বের সমস্যায় AI সাধারণত যেসব ভুল করে

DP-র কোড যাচাইয়ের চেকলিস্ট

• একটি ছোট ইনপুটে পুরো টেবিল হাতে ভরে কোডের টেবিল ছাপিয়ে মিলিয়েছি
• খালি স্ট্রিং, এক অক্ষর, দুই স্ট্রিং একই, কোনো মিল নেই, একটি matrix — এই edge case-গুলো চালিয়েছি
• ছোট এলোমেলো ইনপুটে সব subsequence বা সব বন্ধনী গুনে বের করা brute force-এর সাথে stress testing করেছি
• পুনর্গঠিত উত্তর আলাদাভাবে যাচাই করেছি: LCS দুই স্ট্রিংয়েরই subsequence, অপারেশন প্রয়োগে সত্যিই লক্ষ্য-স্ট্রিং হয়, বন্ধনীর খরচ গুনে m[1][n]-এর সমান
• সবচেয়ে বড় ইনপুটে টেবিলের মেমরি (ঘর × বাইট) আর খরচের মানের overflow হিসাব করেছি