最长公共子序列的界限

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倍！

cimport cython 
from libc.stdlib cimport malloc, free 

def lcs(x, y): 
    cdef int s_x 
    cdef int s_y 
    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 

    cdef int i 

    temp_y_previous = s_x*[0] 
    cdef int *y_previous 
    y_previous = <int *>malloc(s_x*cython.sizeof(int)) 
    if y_previous is NULL: 
     raise MemoryError() 
    for i in xrange(s_x): 
     y_previous[i] = temp_y_previous[i] 

    cdef char *cx 
    cx = <char *>malloc(s_x*cython.sizeof(char)) 
    if cx is NULL: 
     raise MemoryError() 
    i=0 
    for character in x: 
     cx[i]=ord(character) 
     i+=1 

    cdef char *cy 
    cy = <char *>malloc(s_y*cython.sizeof(char)) 
    if cy is NULL: 
     raise MemoryError() 
    i=0 
    for character in y: 
     cy[i]=ord(character) 
     i+=1 

    cdef int k=0 
    cdef int left_value 
    cdef int diagonal_value 
    cdef int n 
    cdef str y_char 
    cdef str x_char 
    while k<s_y: 
     left_value = 0 
     diagonal_value = 0 
     n=0 
     while n<s_x: 
      if cy[k]==cx[n]: 
       left_value = diagonal_value+1 
      else: 
       if left_value<y_previous[n]: 
        left_value = y_previous[n] 
      diagonal_value = y_previous[n] 
      y_previous[n] = left_value 
      n+=1 
     k+=1 
    with nogil: 
     free(y_previous) 
     free(cx) 
     free(cy) 
    return y_previous[s_x-1] 

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') 

输出

11 

编辑

我也尝试用你的代码。我认为中等字符串速度很慢，因为您的函数使用相同的参数调用lcs_len_rec函数。想想缓存/带装饰memoize的那样：

import functools 

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