最长公共子序列的界限

CnR 发表于 Dev

碳纳米管

我需要找到递归最长公共子序列问题（仅它的长度）的最紧密边界（最坏的情况）。我的意思是按照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)))

皮特·达布科夫斯基

这是我能够用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]