最长公子序列界

Question

我需要找到递归最长公共子序列问题的最紧界（最坏情况下）（只有它的长度）。我的意思是复杂度是m和n的界限，m是字符串s的长度，n是字符串t的长度。有人能帮我吗？在

代码是：

def lcs_len_v1(s, t): 
    n = len(s)
    m = len(t)
    return lcs_len_rec(s,n,t,m)

def lcs_len_rec(s,size_s,t,size_t):

    if size_s==0 or size_t==0: #if one of the strings is empty
        return 0

    if s[0] == t[0]: #if we find a common char
        return lcs_len_rec(s[1:],len(s[1:]), t[1:],len(t[1:]))+1
    else:
        return max(lcs_len_rec(s,len(s),t[1:],len(t[1:])), lcs_len_rec(s[1:],len(s[1:]),t,len(t)))

Answer 1

这是我用Python编写的最快的实现：

def lcs(x, y):
    '''returns the length of longest common subsequence of x and y.
       >>> lcs('abcde','aebd')
       3
    '''
    s_x, s_y = len(x), len(y)
    if s_x>s_y: 
        x, y = y, x
        s_x, s_y = s_y, s_x
    y_previous = s_x*[0]
    for y_char in y:
        left_value = 0
        diagonal_value = 0
        n=0
        for x_char in x:
            up_value = y_previous[n]
            if y_char==x_char:
                left_value = diagonal_value+1
            else:
                if left_value<up_value: 
                    left_value = up_value 
            diagonal_value = up_value
            y_previous[n] = left_value 
            n+=1
    return y_previous[-1]

如果你想提高性能，你可以用Cython编译它。它跑得快90倍！在

^{pr2}$

Answer 2

我想这会管用的。但我也认为这对长弦来说很慢。在

def max_common_str_len(s, t):
     if len(s) > len(t):
         return max_common_str_len(t, s)
     for length in range(len(s),0,-1):
         for offset in range(len(s)-length+1):
             if s[offset:offset+length] in t:
                 return length
     else:
         return 0

max_common_str_len('there is a house in new orleans', 'this is a house')

输出

^{pr2}$

编辑

我也用你的代码做了实验。我认为对于中等字符串来说这是很慢的，因为您的函数使用相同的参数调用lcs_len_rec-函数。想一想，用一个装饰器把它藏起来：

import functools

@functools.lru_cache(maxsize=None)
def lcs_len_rec(###your code###