首页 > 试题广场 >

最长公共子序列

[编程题]最长公共子序列

热度指数：6439 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。
例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。
现在给你两个任意字符串（不包含空格），请帮忙计算它们的最长公共子序列的长度。

输入描述:

输入包含多组数据。

每组数据包含两个字符串m和n，它们仅包含字母，并且长度不超过1024。

输出描述:

对应每组输入，输出最长公共子序列的长度。

示例1

输入

abcfbc abfcab
programming contest
abcd mnp

输出

4
2
0

算法知识视频讲解

Python

TimeMac

差劲，对Python那么不友好。根本提交不上去。查看提交过代码的同学，没一个Python的-_-

不加循环输入就说输出为空，加了循环后又说超时或算法复杂度过大？？？

try:
    while True:
        string1,string2 = input().split()
        result = [[0 for i in range(len(string2)+1)] for j in range(len(string1)+1)]
        #result[i][j]保存string1前i个子串和string2前j个子串的公共子序列
        for i in range(1,len(string1)+1):
            for j in range(1,len(string2)+1):
                result[i][j] = max(result[i-1][j],result[i][j-1])
                if string1[i-1]==string2[j-1]:
                    result[i][j] = result[i-1][j-1]+1    #等于子串都减一的公共子序列长度加一
        print(result[-1][-1])
except Exception:
    pass

编辑于 2018-09-23 20:35:56 回复(1)

Python

offer到碗里

#在编译器上可以成功运行，在牛客上总是提示运行超时，不知道怎么办了
while True:
    try:
        A, B = map(str, raw_input('').split())
        n = len(A)
        m = len(B)
        matrix = [0] * m * n
        for i in range(n):
            if A[i] == B[0]:
                for j in range(i, n):
                    matrix[j] = 1
        for i in range(m):
            if B[i] == A[0]:
                for j in range(i, m):
                    matrix[j * n] = 1
        for i in range(1, m):
            for j in range(1, n):
                if B[i] == A[j]:
                    matrix[i * n + j] = max(matrix[(i - 1) * n + j - 1] + 1, matrix[(i - 1) * n + j], matrix[i * n + j - 1])
                else:
                    matrix[i * n + j] = max(matrix[(i - 1) * n + j], matrix[i * n + j - 1])
        print matrix[m * n - 1]
    except:
        break

发表于 2018-01-24 11:00:00 回复(1)

Python

智．之水叶神


# -*- encoding:utf -*-
import sys
def solution(s1,s2,j,i,res,l1,l2):
	if j==l1 or i==l2:
		return res
	else:
		if s2[i] in s1[j:]:
			n1=solution(s1,s2,j,i+1,res,l1,l2)
			while j < l1:
				if s1[j]==s2[i]:break
				else:j+=1
			n2=solution(s1,s2,j,i+1,res+1,l1,l2)
			return max(n1,n2)
		else:
			return solution(s1, s2, j, i+1, res,l1,l2)
if __name__ == "__main__":
	s1, s2 = map(str, raw_input().split())
	l1 = len(s1)
	l2 = len(s2)
	s3=""
	for i in xrange(l2):
		if s2[i] in s1:s3+=s2[i]
	#print s3
	s2=s3
	l2 = len(s2)
	n=solution(s1,s2,0,0,0,l1,l2)
	print n

为什么在自己的电脑上测试用例可以通过，但是提交给系统却提示返回值为空？

编辑于 2017-08-22 09:24:18 回复(0)