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<cstdio>

#include<cstring>

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\n",dp[len_a][len_b]);

	}

}

滚动数组优化空间：

设dp1为前一列，dp2为后面一列。

#include<cstdio>

#include<cstring>

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\n",dp1[len_b]);

	}

}

巴特西

POJ 1458 Common Subsequence (zoj 1733 ) LCS

最新文章

热门文章