最長共通部分列(LCS) - 似非学問的な手記

最近更新が滞っている……
なんとかせねば（；ﾟωﾟ）

なので少し細かな話題をば。
最長共通部分列問題（LCS）というものは、まあ動的計画法(DP)を学ぶとしたらまず確実に練習問題で出される問題で、「二つの文字列の共通部分列のうち最長のものの長さを求めよ」という内容です。

「部分列」なので、文字の取り方は文字列からとびとびになってもかまいません。
"abfhfr"の部分列として"aff"とかもアリです。
ただし、順番を変えてはダメ。

この問題を解くには、あまりにも有名な次のアルゴリズムがあります。

文字列str1(長さn)とstr2(長さm)に対し、

(1)二次元配列DPを用意する。
(2)DP[0][0〜m]とDP[0〜n][0]を0で初期化。
(3)二重ループでi,jを動かして、各DP[i][j]を
DP[i][j]=
max{
　　　　　DP[i-1][j],
　　　　　DP[i][j-1],
　　　　　(str1[i-1][j-1]==str2[i-1][j-1]のとき)DP[i-1][j-1]
}
で計算する。

DP[i][j]というのは「str1のi文字目まで」と「str2のj文字目まで」の最長共通部分列です。
条件「str1[i-1][j-1]==str2[i-1][j-1]」が成り立てば共通部分列を伸ばせるというわけですね。

で、なんで今こんな記事を書いているかというと、このアルゴリズムで「二つの文字列の共通部分列のうち最長のもの」そのものを出力するプログラムをうろ覚えで覚えていたので、その覚書をしておきたかったわけなのです。

通称「トレースバック」と呼ばれるアルゴリズムは、さっきのアルゴリズムにちょっと足すだけでできる。

文字列str1(長さn)とstr2(長さm)に対し、

(1)二次元配列DPと、二次元配列TRACE
用意する。

(2)DP[0][0〜m]とDP[0〜n][0]を0で初期化し、
TRACE[0][0〜m]とTRACE[0〜n][0]をENDで初期化。
(3)二重ループでi,jを動かして、各DP[i][j],TRACE[i][j]を
(DP[i][j],TRACE[i][j])=
max{
　　　　　(DP[i-1][j],HORIZONTAL),
　　　　　(DP[i][j-1],VERTICAL),
　　　　　(str1[i-1][j-1]==str2[i-1][j-1]のとき)(DP[i-1][j-1],DIAGONAL)
}
で計算する。ただし、関数maxはDPの大きさを比較する。

さらに、TRACEを用いてLCSを次の関数printLCS(i,j)で表示。呼び出しはprintLCS(n,m)

printLCS(i,j)
Case 1:TRACE[i][j]=HORIZONTAL
　　　　　printLCS(i-1,j)
Case 2:TRACE[i][j]=VERTICAL
　　　　　printLCS(i,j-1)
Case 3:TRACE[i][j]=DIAGONAL
　　　　　printLCS(i-1,j-1)
　　　　　文字str1[i-1]を表示
Case 4:TRACE[i][j]=END
　　　　　return

俺はてっきりTRACEには文字そのものを格納するもんだと勘違いしてましたとさ。それじゃ辿れないじゃんorz

なんだかんだで書いたコードがこちら。

#include<iostream>
#include<string>
#define VERTICAL 0
#define HORIZONTAL 1
#define DIAGONAL 2
#define END 3
using namespace std;

void printLCS(string str1,string str2,char **trace,int n,int m){
	switch(trace[n][m]){
		case END:
			return;
		case HORIZONTAL:
			printLCS(str1,str2,trace,n-1,m);
			break;
		case VERTICAL:
			printLCS(str1,str2,trace,n,m-1);
			break;
		case DIAGONAL:
			printLCS(str1,str2,trace,n-1,m-1);
			cout<<str1[n-1];
			break;
	};
	return;
}

int main(){
	string str1,str2;
	int **dp;
	char **trace;
	int n,m;
	cin>>str1>>str2;
	n = str1.length();
	m = str2.length();
	
	//DPメモ用二次元メモリ確保
	dp = new int*[n+1];
	for(int i=0;i<=n;i++){
		dp[i] = new int[m+1];
	}
	//Traceback用メモリ確保
	trace = new char*[n+1];
	for(int i=0;i<=n;i++){
		trace[i] = new char[m+1];
	}
	
	////DP本体
	
	//初期化
	for(int i=0;i<=n;i++){
		dp[i][0]=0;
		trace[i][0]=END;
	}
	for(int j=0;j<=m;j++){
		dp[0][j]=0;
		trace[0][j]=END;
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(str1[i-1]==str2[j-1] && dp[i-1][j-1]>dp[i-1][j]-1 && dp[i-1][j-1]>dp[i][j-1]-1){
				dp[i][j] = dp[i-1][j-1]+1;
				trace[i][j] = DIAGONAL;
			}else if(dp[i][j-1]>dp[i-1][j]){
				dp[i][j] = dp[i][j-1];
				trace[i][j] = VERTICAL;
			}else{
				dp[i][j] = dp[i-1][j];
				trace[i][j] = HORIZONTAL;
			}
		}
	}
	cout<<"LCS between "<<str1<<" and "<<str2<<" is ";
	printLCS(str1,str2,trace,n,m);
	cout<<endl;
	cout<<"Length :"<<dp[n][m]<<endl;
	
	//DPメモ用メモリ解放
	for(int i=0;i<=n;i++){
		delete [] dp[i];
	}
	delete [] dp;
	//Traceback用メモリ解放
	for(int i=0;i<=n;i++){
		delete [] trace[i];
	}
	delete [] trace;
	
	return 0;
}

そういえば、C++のnewで一度に多次元配列型のメモリを確保するのはさすがに無理のようですね。
一度にdelete出来ないのは知ってたけど。

今日はこの辺で。
今日からしばらくは頻繁に更新するかも？
（・ω・）ﾉｼ　予定は未定〜