游客 注册 | 登录
中文 | En

3970 - 【二维一边推1.1】最长公共子序列 LCS加强版

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB
给出两个字符串 S1 和 S2 求它们最长公共子序列的长度。
什么是最长公共子序列呢？
    比如：
        S1:='abbccdss'
        S2:='aeebfcaadb'
    那么S1和S2的最长公共子序列就是："abcd". 这个说明最长公共子序列强调位置的前后关系不变，但不在乎是否连续。另外 最长公共子序列不唯一。任意输出一个最长的公共子序列即可。
【输入格式】

读入两行，分别是S1和S2（ 长度不大于1000）。
【输出格式】
输出一个整数。即为最长公共子序列的长度。

 【输入样例】

abbccdss
aeebfcaadb

【输出样例】
4
abcd

题目输入

题目输出

输入/输出样例

输入格式


                        

                        

                            
输出格式

                            

                        


                        
                                            


                                        
                    

						                                                        
                                                            
C++解答

                                
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

struct node
{
	int x,y;
}p[1001][1001];

char s1[1100], s2[1100],s[1100];

int f[1100][1100],len1,len2;

int mymax ( int x, int y ){ return x > y ? x : y; }

int main ()
{
	
    scanf ( "%s", s1 + 1 ); len1 = strlen ( s1 + 1 );
    scanf ( "%s", s2 + 1 ); len2 = strlen ( s2 + 1 );
    memset(f,0,sizeof(f));
    
    for (int i = 1; i <= len1; i ++ )
	{
        for (int j = 1; j <= len2; j ++ )
		{
            if ( s1[i] == s2[j] )
			{
                f[i][j] = f[i - 1][j - 1] + 1;
                p[i][j].x=i;
                p[i][j].y=j;
            }
            else
			{
                if( f[i-1][j]  >  f[i][j-1] )
                {
                	f[i][j]=f[i-1][j];
                	p[i][j]=p[i-1][j];
                }
                else
                {
                	f[i][j]=f[i][j-1];
                	p[i][j]=p[i][j-1];
                }
            }
        }
    }
    printf ( "%d\n", f[len1][len2] );
    
    int x=len1,y=len2,len=0;
    
    while( f[x][y]>0)
    {
    	int xx,yy;
    	xx=x;yy=y;
    	s[++len]=s1[   p[xx][yy].x   ];// s[++len]=s2[ p[xx][yy].y];
    	x=p[xx][yy].x-1;
    	y=p[xx][yy].y-1;
    }
    for(int i=len;i>=1;i--) printf("%c",s[i]);
    printf("\n");
    return 0;
}




                                                                                    
                                                                        
                    
                
                
            

            

                

                

                    

                        







                    


                    

                        请先登陆