南阳理工OJ 36 最长公共子序列

连接： http://acm.nyist.net/JudgeOnline/problem.php?pid=36

 

最长公共子序列

时间限制：3000 ms  |  内存限制：65535 KB

难度：3

 

描述

咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列。
tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

 

输入

第一行给出一个整数N(0<N<100)表示待测数据组数
接下来每组数据两行，分别为待测的两组字符串。每个字符串长度不大于1000.

输出

每组测试数据输出一个整数，表示最长公共子序列长度。每组结果占一行。

样例输入

2
asdf
adfsd
123abc
abc123abc

样例输出

3
6

 

 

动态规划：p[i][j]表示第一个串的第i个和第二个串的j比较时的最优解

如果  str1[i]==str2[j]   则p[i][j]=p[i-1][j-1]+1;

否则  p[i][j]=max( p[i-1][j]  ,  p[i][j-1] );

然后  p[len1][len2]就是要求的结果啦！

 

#include<string.h>
#include<stdio.h>
#define max(a,b) a>b?a:b
int p[1010][1010];
int main()
{
       int T,i,j,len1,len2;
       char str1[1010];
       char str2[1010];
       scanf("%d",&T);
       while(T--)
       {
              memset(p,0,sizeof(p));
              scanf("%s%s",str1,str2);
              len1=strlen(str1);
              len2=strlen(str2);
              for(i=0;i<len1;i++)
              {
                     for(j=0;j<len2;j++)
                     {
                            if(str1[i]==str2[j])p[i+1][j+1]=1+p[i][j];
                            else p[i+1][j+1]=max(p[i][j+1],p[i+1][j]);
                     }
              }
              printf("%d\n",p[len1][len2]);
       }
       return 0;
}

 

这种方法比较笨拙，因为在比较第一个串的第i个时，第二个串只需用到p[i-1][j]或者p[i][j]  （j:1~len2）这两行数，而上面却用到了len1*len2的二维数组，下面的方法是运用滚动数组来优化。可以省下大量的时间和空间（建议在可以看懂第一种的前提下在看这种方法）

 

#include <stdio.h>
#include <string.h>
#define max(a,b) (a)>(b) ? (a) : (b)

char a[1005], b[1005];
short int up[1005], dab[1005];//up存放上一行的数，dad存放新一行的数
short int t, la, lb;

int dp(void)
{
	int i, j;

	memset(up, 0, sizeof(up));
	memset(dab, 0, sizeof(dab));
	for (i = 0; i < la; i++)//两个循环还是一样
	{
		for (j = 0; j < lb; j++)
		{
			if (a[i] == b[j])//如果第一个串的第i个和第二个串的第j个相等
				dab[j+1] = up[j]+1;//就在上一行j-1的基础上加1
			else
				dab[j+1] = max(up[j+1], dab[j]);//否则就取上一行的第j个位置和这一行的第j-1的位置的最大值
		}
		for (j = 0; j <= lb; j++)//数组滚动，更新上一行的数组
			up[j] = dab[j];
	}
	return dab[lb];//返回结果
}

int main()
{
	scanf("%hd", &t);
	while (t--)
	{
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		scanf("%s%s", a, b);
		la = strlen(a);
		lb = strlen(b);
		printf("%hd\n", dp());
	}
	return 0;
}

 

题到此也就告一段落了，但仔细想想，上面的方法其实还是可以在次优化的，每次在找p[i][j]时，用到的只有p[i-1][j-1]  、p[i][j-1] 、 p[i-1][j]  这些值，我们找个变量把它们存起来就好了，如果只用一个数组p[j]在写

p[i-1][j]和p[i][j]其实就是p[j]一个人，只不过是在更新之前当做p[i-1][j]用，更新之后就变成了p[i][j],大家慢慢体会吧、

下面这种做法又优化了大量的时间和空间

 

#include <cstdio>
#include<cstring>
#define max(x,y)  x>y?x:y
char a[1005],b[1005];
int f[1005];
int main()
{
  int T,la,lb,k,k1,i,j;
  scanf("%d",&T);
  while(T--)
  {
      memset(f,0,sizeof(f));
      scanf("%s%s",a,b);
      la=strlen(a);
      lb=strlen(b);
      for(i=0;i<la;i++)
          for(j=0,k1=0;j<lb;j++)
          {   k=f[j+1];//k保存上一行的第j个位置的值
              if(a[i]==b[j]) f[j+1]=k1+1;
              else if(f[j]>f[j+1]) f[j+1]=f[j];//f[j+1]有双重的身份，比较前是上一行的值，比较后就是新一行的值啦！慢慢理解吧
              k1=k;//k1保存上一行的个j-1个位置的值
          }
          printf("%d\n",f[lb]);
  }
}