طولانی‌ترین زیردنباله‌ی مشترک

دو سری از اعداد به شما داده شده است. یک زیردنباله‌ی مشترک، دنباله‌ای است که زیردنباله‌ی هر‌ دو سری اعداد باشد. شما باید طول بزرگ‌ترین زیردنباله‌ی مشترک این دو سری که به شما داده شده است را حساب کنید.
مثلا دنباله‌ی ۱،۵،۳ یک زیردنباله از دنباله‌ی ۱،۲،۵،۴،۷،۳ است. اما ۱،۳،۵ زیردنباله‌ی همان دنباله نیست. همچنین ۲،۵ هم یک زیردنباله‌‌ی ۱،۲،۷،۳،۵ و هم زیردنباله‌ی ۲،۵،۷ است پس یک زیر دنباله‌ی مشترک این دو است و طول آن هم دو است چون دو عضو دارد و بزرگ‌ترین زیر‌دنباله‌ی مشترک این دو دنباله نیز هست، چون این دنباله‌ها زیردنباله‌ای به طول سه ندارند.

برای حل این مسئله از روش برنامه‌ریزی پویا استفاده می‌کنیم.
آرایه‌ی $d$ یک آرایه‌ی دو بعدی به ابعاد $(n+1) \times (m+1)$ است که در آن $n$ و $m$ طول دو سری ورودی اند. مقدار $d_{i,j}$ برابر طول بزرگ‌ترین زیردنباله‌ی مشترک بین $i$ خانه‌ی اول از سری اول و $j$ خانه‌ی اول سری دوم است. $a_i$ و $b_i$ را به ترتیب عنصر $i$ ام دنباله‌ی اول و دوم در نظر بگیرید. پس جواب مسئله برابر $d_{n,m}$ است.
مقدار اولیه: مقدار تمام خانه‌های $d_{i,0}$ و $d_{0,j}$ برابر صفر است. چون طول بزرگ‌ترین زیردنباله‌ی مشترک بین دنباله‌ی تهی با هر دنباله‌ی دیگری برابر صفر است.
به روز رسانی: برای به دست آوردن مقدار $d_{i,j}$ خود این بزرگ‌ترین زیردنباله‌ی مشترک (که طولش$d_{i,j}$ است) را در نظر بگیرید. این زیردنباله :

1. یا هر دو‌ی $a_i$ و $b_j$ را شامل می‌شود که این حالت فقط در صورتی می‌تواند اتفاق بیافتد که $a_i = b_j$ باشد. در این حالت جواب برابر $d_{i-1,j-1} + 1$ است.
2. یا شامل$a_i$ نیست. درنتیجه مقدارش برابر $d_{i-1,j}$ است.
3. یا شامل $b_j$ نیست. درنتیجه مقدارش برابر $d_{i,j-1}$ است.

پس اگر $a_i = b_j$: $$ d_{i,j} = max( d_{i-1,j-1} + 1 , d_{i-1,j} , d_{i,j-1} ) $$ در غیر اینصورت: $$ d_{i,j} = max( d_{i-1,j} , d_{i,j-1} ) $$ شبه کد:

for i from 0 to n 
	d[i][0] = 0 
for j from 0 to m 
	d[0][j] = 0 

for i from 1 to n 
	for j from 1 to m 
		d[i][j] = max( d[i-1][j] , d[i][j-1] ) 
		if   a[i] == b[j] 
			d[i][j] = max( d[i][j] , d[i-1][j-1] + 1 ) 

برای این که خود بزرگ‌ترین زیردنباله‌ی مشترک را هم پیدا کنیم، می‌توانیم یک آرایه‌ی دوبعدی همانند $d$ درست کنیم که نشان بدهد هر خانه از آرایه از کدام روش (۱ یا ۲ یا ۳) مقداردهی شده و در پایان مسیر پر شدن $d$ را پیدا کرده و زیردنباله را پیدا کنیم.

حافظه از $O(n^2)$ است اما از آنجایی که برای محاسبه‌ی هر ردیف از آرایه‌ی $d$ فقط به ردیف قبلی احتیاج داریم، احتیاجی به حافظه‌ی $O(n^2)$ نیست و حافظه‌ی $O(n)$ کافی است. اما اگر بخواهیم خود زیردنباله‌ی مشترک را به دست آوریم، به حافظه‌ی $O(n^2)$ نیاز است.
اما در هر صورت $O(n^2)$ مقدار باید محاسبه شوند و هزینه‌ی محاسبه‌ی هر کدام $O(1)$ است. پس پیچیدگی زمانی الگوریتم از $O(n^2)$ است.

LCS.cpp

#include <iostream> 
#include <vector> 
using namespace std; 
 
const int MAXN = 10*1000; 
 
int d[2][MAXN+10];  // there is no use in using a 1D array here. just for the demonstration 
int p[MAXN+10][MAXN+10]; // parent. for writing out the LCS
 
int a[MAXN+10]; // 1-base for simplicity 
int b[MAXN+10]; // 1-base 
 
// just for finding the real subsequence with parents 
int X[3] = { 1 , 1 , 0 }; 
int Y[3] = { 1 , 0 , 1 }; 
 
int main(){ 
	ios::sync_with_stdio(false); 
	int n, m; 
	cin >> n; 
	for(int i=1; i<=n; i++) 
		cin >> a[i]; 
	cin >> m; 
	for(int i=1; i<=m; i++) 
		cin >> b[i]; 
 
	int k=0; 
	// all the values of d are zero, so no need to initialization 
	for(int i=1; i<=n; i++){ 
		for(int j=1; j<=m; j++){ 
			d[k][j] = d[!k][j]; 
			p[i][j] = 1;  // remember the case numbers 
			if( d[k][j-1] > d[k][j] ){ 
				d[k][j] = d[k][j-1]; 
				p[i][j] = 2; 
			} 
			if( a[i] == b[j] && d[!k][j-1] + 1 > d[k][j] ){ 
				d[k][j] = d[!k][j-1] + 1; 
				p[i][j] = 0; 
			} 
		} 
		k = !k; 
	} 
 
	cout << d[!k][m] << endl; 
 
	vector<int> out; 
	int x=n, y=m; 
	while( x > 0 && y > 0 ){ 
		int parent_val = p[x][y]; 
		if( parent_val == 0 ) 
			out.push_back(a[x]); 
 
		x -= X[parent_val]; 
		y -= Y[parent_val]; 
	} 
 
	for(int i=(int)out.size()-1; i>=0; i--) 
		cout << out[i] << " "; 
	cout << endl; 
 
	return 0; 
}

• DNA Sequences
• CF[10D] LCIS