POJ 1458 Common Subsequence (zoj 1733 ) LCS

題目大意：

給定兩串子序列，求最長的公共字串（LCS）

設d( i , j)為A和 B的LCS的長度，則當A[i] = B[j]時， d(i , j)= d(i-1, j-1)+1 ; 否則 d (i , j)=max ( d(i - 1 ,j) , d(i , j-1 )}，時間復雜度為O(nm)，n和m分別為序列A和B的長度。

可用滾動數組優化空間復雜度。

下面給出不用和用滾動數組的。

空間未用滾動數組優化版本。。。。

#include
#include
const int MAXN=512;
char a[MAXN],b[MAXN];
int dp[MAXN][MAXN];
int main()
{
	while(~scanf(%s%s,a+1,b+1))
	{
		memset(dp,0,sizeof(dp));
		int len_a=strlen(a+1);
		int len_b=strlen(b+1);
		for(int i=1;i<=len_a;i++)
		{
			for(int j=1;j<=len_b;j++)
			{
				if(a[i] == b[j])				
					dp[i][j]= dp[i-1][j-1]+1;			
				else
					dp[i][j]= dp[i][j-1] > dp[i-1][j]? dp[i][j-1] : dp[i-1][j];
			}
		}
		printf(%d
,dp[len_a][len_b]);
	}
}

滾動數組優化空間：

設dp1為前一列，dp2為後面一列。

#include
#include
const int MAXN=512;
char a[MAXN],b[MAXN];
int dp1[MAXN],dp2[MAXN];
int main()
{
	while(~scanf(%s%s,a+1,b+1))
	{
		memset(dp1,0,sizeof(dp1));
		memset(dp2,0,sizeof(dp2));
		int len_a=strlen(a+1);
		int len_b=strlen(b+1);
		for(int i=1;i<=len_a;i++)
		{		

			for(int j=1;j<=len_b;j++)
			{
				if(a[i] == b[j])				
					dp2[j]= dp1[j-1]+1;			
				else
					dp2[j]= dp2[j-1] > dp1[j]? dp2[j-1] : dp1[j]; 
			}

			memcpy(dp1,dp2,sizeof(dp2));

		}
		printf(%d
,dp1[len_b]);
	}
}