游客 注册 | 登录
中文 | En

1097 - 最长公共子序列

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

给你一个序列X和另一个序列Z，当Z中的所有元素都在X中存在，并且在X中的下标顺序是严格递增的，那么就把Z叫做X的子序列。
例如：Z=<a,b,f,c>是序列X=<a,b,c,f,b,c>的一个子序列，Z中的元素在X中的下标序列为<1,2,4,6>。
现给你两个序列X和Y，请问它们的最长公共子序列的长度是多少？

题目输入

输入包含多组测试数据。每组输入占一行，为两个字符串，由若干个空格分隔。每个字符串的长度不超过100。

题目输出

对于每组输入，输出两个字符串的最长公共子序列的长度。

输入/输出样例

输入格式

abcfbc abfcab
programming contest 
abcd mnp

输出格式

4
2
0

C语言解答

#include<stdio.h>
#include<string.h>

int a[101][101];

int LCS(const char *s1,const char *s2)
{
	int m=strlen(s1),n=strlen(s2);
	int i,j;
	a[0][0]=0;
	for(i=1;i<=m;++i)
		a[i][0]=0;
	for(i=1;i<=n;++i)
		a[0][i]=0;
	for(i=1;i<=m;++i)
		for(j=1;j<=n;++j)
		{
			if(s1[i-1]==s2[j-1])
				a[i][j]=a[i-1][j-1]+1;
			else if(a[i-1][j]>a[i][j-1])
				a[i][j]=a[i-1][j];
			else
				a[i][j]=a[i][j-1];
		}
	return a[m][n];
}

int main()
{
	char s1[101],s2[101];
	while(scanf("%s%s",s1,s2)!=EOF)
		printf("%d\n",LCS(s1,s2));
	return 0;
}

C++解答

#include<stdio.h>
#include<string.h>

int a[101][101];

int LCS(const char *s1,const char *s2)
{
	int m=strlen(s1),n=strlen(s2);
	int i,j;
	a[0][0]=0;
	for(i=1;i<=m;++i)
		a[i][0]=0;
	for(i=1;i<=n;++i)
		a[0][i]=0;
	for(i=1;i<=m;++i)
		for(j=1;j<=n;++j)
		{
			if(s1[i-1]==s2[j-1])
				a[i][j]=a[i-1][j-1]+1;
			else if(a[i-1][j]>a[i][j-1])
				a[i][j]=a[i-1][j];
			else
				a[i][j]=a[i][j-1];
		}
	return a[m][n];
}

int main()
{
	char s1[101],s2[101];
	while(scanf("%s%s",s1,s2)!=EOF)
		printf("%d\n",LCS(s1,s2));
	return 0;
}

Java解答


import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.Scanner;
    

class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext())
		{
			
		
			String s1 = scanner.next();
			String s2 = scanner.next();
			Integer[][]b = new Integer[102][102];
			Integer[][]c = new Integer[102][102];
			int m ,n;
			m = s1.length();
			n = s2.length();
			int result = LCSLength(s1.toCharArray(),s2.toCharArray(),m,n,c,b);
			System.out.println(result);
		}
	}
	
	
	public static int LCSLength(char[] x, char[] y, int m, 
			int n, Integer[][] c, Integer[][] b)
	{
		int i ,j;
		
		for(i = 0; i <= m; i++)
			c[i][0] = 0;
		for(i = 1; i <= n; i++)
			c[0][i] = 0;
		for(i = 1; i <= m; i++)
		{
			for(j = 1; j <= n; j++)
			{
				if(x[i - 1] == y[j - 1])
				{
					c[i][j] = c[i - 1][j - 1] + 1;
					b[i][j] = 0;
				}
				else if(c[i - 1][j] >= c[i][j - 1])
				{
					c[i][j] = c[i - 1][j];
					b[i][j] = 1;
				}
				else
				{
					c[i][j] = c[i][j - 1];
					b[i][j] = -1;
				}
			}
		}
		return c[m][n];
	}
	

}

Python解答

#coding=utf-8
def Matrix(rows,cols):
    matrix = [[[0,'#'] for col in range(cols+1)] for row in range(rows+1)]
    return matrix
def printf(lst,str1,str2):
    (rows,cols)=(len(str1),len(str2))
    print ' '*6,
    for tmp in str2:
        print '%s  ' % tmp,
    print
    print ' '*2,
    for j in range(cols+1):
            print '%d:%s' % (lst[0][j][0],lst[0][j][1]),
    print 
    for i in range(1,rows+1):
        print '%s ' % str1[i-1],
        for j in range(cols+1):
            print '%d:%s' % (lst[i][j][0],lst[i][j][1]),
        print
    

while True:
    [x,y]=raw_input().split()
    (m,n)=(len(x),len(y))
    mat = Matrix(m,n)#已经经过初始化
    for i in range(1,m+1):
        for j in range(1,n+1):
            #print "i=%d,j=%d" %(i,j)
            if x[i-1]==y[j-1]:
                mat[i][j][0]=mat[i-1][j-1][0]+1
                mat[i][j][1]='↖'
            elif mat[i-1][j][0]>=mat[i][j-1][0]:
                mat[i][j][0]=mat[i-1][j][0]
                mat[i][j][1]='↑'
            else:
                mat[i][j][0]=mat[i][j-1][0]
                mat[i][j][1]='←'
    #printf(mat,x,y)
    print mat[m][n][0]
请先登陆