Сложность решения этого с помощью рекурсивного кода

Question

Мне нужно найти длину самой длинной общей подпоследовательности.

s и t являются String с, и n и m являются их длиной. Я бы хотел написать рекурсивный код.

Это то, что я сделал до сих пор, но я не могу получить никакого прогресса:

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): 
    cnt= 0 
    if size_s==0 or size_t==0: 
     return 0 
    elif s[0]==t[0]: 
     cnt= +1 
    return cnt, lcs_len_rec(s[1:], len(s[1:]), t[1:], len(t[1:])) 

Answer 1

Это работает:

def lcs(xstr, ystr): 
    if not xstr or not ystr: 
     return "" 
    x, xs, y, ys = xstr[0], xstr[1:], ystr[0], ystr[1:] 
    if x == y: 
     return x + lcs(xs, ys) 
    else: 
     return max(lcs(xstr, ys), lcs(xs, ystr), key=len) 

print(lcs("AAAABCC","AAAACCB")) 
# AAAACC 

Вы должны знать, что рекурсивный подход будет работать только с относительно тривиальной строкой; complexity очень быстро увеличивается с более длинными строками.

Answer 2

Используя метод memoization, вы можете запустить алгоритм также с очень длинными строками. Infact это только O (N^2):

def recursiveLCS(table, s1, s2): 
    if(table[len(s1)][len(s2)] != False): 
     return table[len(s1)][len(s2)] 
    elif len(s1) == 0 or len(s2) == 0: 
     val = "" 
    elif s1[0] == s2[0]: 
     val = s1[0] + recursiveLCS(table, s1[1:], s2[1:]) 
    else: 
     res1 = recursiveLCS(table, s1[1:], s2) 
     res2 = recursiveLCS(table, s1, s2[1:]) 
     val = res2 
     if len(res1) > len(res2): 
      val = res1 
    table[len(s1)][len(s2)] = val 
    return val 

def computeLCS(s1, s2): 
    table = [[False for col in range(len(s2) + 1)] for row in range(len(s1) + 1)] 
    return recursiveLCS(table, s1, s2) 

print computeLCS("testistest", "this_is_a_long_testtest_for_testing_the_algorithm") 

Выход:

teststest 

Answer 3

это мой код, как я могу использовать на нем технику запоминания?

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: 
     return 0 
    elif s[0]==t[0]: 
     cnt=0 
     cnt+= 1 
     return cnt+ lcs_len_rec(s[1:], size_s-1, t[1:], size_t-1) 
    else: 
     return max(lcs_len_rec(s[1:], size_s-1, t, size_t), lcs_len_rec(s, size_s, t[1:], size_t-1))