Блог

Есть ли встроенная функция в python, которая возвращает длину самой длинной общей подпоследовательности двух списков?

 a=[1,2,6,5,4,8]
b=[2,1,6,5,4,4]

print a.llcs(b)

>>> 3
  

Я пытался найти самую длинную общую подпоследовательность, а затем получить ее длину, но я думаю, что должно быть лучшее решение.

Вы можете легко преобразовать самую длинную общую подпоследовательность (LCS) в длину самой длинной общей подпоследовательности (LLC):

 def lcs_length(a, b):
    table = [[0] * (len(b)   1) for _ in range(len(a)   1)]
    for i, ca in enumerate(a, 1):
        for j, cb in enumerate(b, 1):
            table[i][j] = (
                table[i - 1][j - 1]   1 if ca == cb else
                max(table[i][j - 1], table[i - 1][j]))
    return table[-1][-1]
  

ДЕМОНСТРАЦИЯ:

 >>> a=[1,2,6,5,4,8]
>>> b=[2,1,6,5,4,4]
>>> lcs_length(a, b)
4
  

Если вам нужна самая длинная общая подстрока (другая, но связанная проблема, когда подпоследовательность является непрерывной), используйте:

 def lcsubstring_length(a, b):
    table = [[0] * (len(b)   1) for _ in range(len(a)   1)]
    longest = 0
    for i, ca in enumerate(a, 1):
        for j, cb in enumerate(b, 1):
            if ca == cb:
                length = table[i][j] = table[i - 1][j - 1]   1
                longest = max(longest, length)
    return longest
  

Это очень похоже на lcs_length подход к динамическому программированию, но мы отслеживаем максимальную длину, найденную на данный момент (поскольку больше не гарантируется, что последний элемент в таблице является максимальным).

Это возвращает 3 :

 >>> lcsubstring_length(a, b)
3
  

Вариант разреженной таблицы, чтобы не нужно было отслеживать все 0 s (используйте это, если a и b потенциально очень большие):

 def lcsubstring_length(a, b):
    table = {}
    longest = 0
    for i, ca in enumerate(a, 1):
        for j, cb in enumerate(b, 1):
            if ca == cb:
                length = table[i, j] = table.get((i - 1, j - 1), 0)   1
                longest = max(longest, length)
    return longest