Longest common subsequence

lcs.cpp

// O(NM)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 100
char a[MAX],b[MAX],result[MAX];
int dp[MAX+1][MAX+1];
int getLcsLen(char a[], char b[])
{ 
	int m=strlen(a), n=strlen(b),i,j;
	for (int i=0;i<=m;i++) 
		dp[i][0]=0;
	for (int i=0;i<=n;i++) 
		dp[0][i]=0;
	for (int i=1;i<=m;i++) 
		for (int j=1;j<=n;j++)
		{
			if (a[i-1]==b[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];
}
void buildLcs(char result[],char a[], char b[])
{ 
	int k, i=strlen(a), j=strlen(b);
	k=getLcsLen(a,b);
	result[k]='\0';
	while(k>0)
	{
		//代表A字串的第i-1字元非必要（A去掉末字元後與B的LCS必定是A、B
		//的一個子字串，所以將此字元去掉後也可得到A、B的子字串），否則
		// 代表子字串必包含此字元
		if (dp[i][j]==dp[i-1][j]) 
			i--;
		else if (dp[i][j]==dp[i][j-1])//代表B字串的第j-1字元非必要，否則代表子字串必包含此字元
			j--;
		else
		//因上述兩個條件都不符，且兩的字元都是在A、B的最後一個
		//，所以此兩字元必定是相等的，則我們把此字元存起來，
		//然後將兩邊的此字元都刪掉，得到的兩個新字串的LCS與此字元
		//連接後必定可得到A、B的LCS
		{
			result[--k]=a[i-1];
			i--; 
			j--;
		}
	}
}
int main()
{ 
	while(scanf("%s%s",a,b)==2)
	{
		buildLcs(result,a,b);
		printf("LCS=%s\n",result);
	}
}