Observe as duas formas abaixo para calcular o comprimento da subsequência comum máxima (LCS = longest common substring) entre dois strings x[0:m] e y[0:n].
- Para que serve a matriz c e o que cada c[i][j] representa?
- Qual a complexidade das funções lcs_rec e lcs_prog_din abaixo?
#---------------------------------------------- def lcs_rec(x, m, y, n): if m == 0 or n == 0: return 0 if x[m-1] == y[n-1]: return lcs_rec(x, m-1, y, n-1) + 1 return max(lcs_rec(x, m-1, y, n), lcs_rec(x, m, y, n-1)) #---------------------------------------------- def lcs_prog_din(x, y): m = len( x ) n = len( y ) c = crie_matriz(m+1,n+1, 0) for i in range(1,m+1): for j in range(1,n+1): if x[i-1] == y[j-1]: c[i][j] = c[i-1][j-1] + 1 else: c[i][j] = max(c[i-1][j], c[i][j-1]) return c[m][n] #---------------------------------------------- def crie_matriz(n_lin, n_col, valor = 0): matriz = [] for i in range(n_lin): matriz.append([valor]*n_col) return matriz