0
0 комментариев

Есть 3 строки. Нужно найти длину наибольшей общей подпоследовательности.

для двух строк я реализовал так:

def lcs(a, b):
lengths = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
# row 0 and column 0 are initialized to 0 already
for i, x in enumerate(a):
    for j, y in enumerate(b):
        if x == y:
            lengths[i+1][j+1] = lengths[i][j] + 1
        else:
            lengths[i+1][j+1] = max(lengths[i+1][j], lengths[i][j+1])
# read the substring out from the matrix
return lengths[len(a)][len(b)]

для трех пробую так же, но через 3 мерную матрицу:

def lcs(a, b, c):
lengths = [[[0 for j in range(len(b) + 1)] for i in range(len(a) + 1)] for k in range(len(c) + 1)]
for i, x in enumerate(a):
    for j, y in enumerate(b):
        for k, z in enumerate(c):
            if x == y == z:
                lengths[i + 1][j + 1][k + 1] = lengths[i][j][k] + 1
            else:
                lengths[i + 1][j + 1][k + 1] = max(lengths[i + 1][j][k], lengths[i][j + 1][k], lengths[i][j][k+1])
return lengths[len(a)][len(b)][len(c)]

но для 3х строк не считает. Как это можно переделать?


Добавить комментарий