[PYTHON] 파이썬 :리스트의 가장 긴 공통 부분 시퀀스의 길이

파이썬 :리스트의 가장 긴 공통 부분 시퀀스의 길이

파이썬에서 두리스트의 가장 긴 공통 서브 시퀀스의 길이를 반환하는 내장 함수가 있습니까?

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

print a.llcs(b)

>>> 3

나는 가장 긴 공통 서브 시퀀스를 찾고 그 길이를 얻으려고했지만 더 나은 해결책이 있어야한다고 생각한다.

해결법

1. ==============================

   1.LCS를 LLCS로 쉽게 다시 만들 수 있습니다.

   LCS를 LLCS로 쉽게 다시 만들 수 있습니다.

   def lcs_length(a, b):
       table = [[0] * (len(b) + 1) for _ in xrange(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 xrange(len(a) + 1)]
       l = 0
       for i, ca in enumerate(a, 1):
           for j, cb in enumerate(b, 1):
               if ca == cb:
                   table[i][j] = table[i - 1][j - 1] + 1
                   if table[i][j] > l:
                       l = table[i][j]
       return l
   

   이는 lcs_length 동적 프로그래밍 접근법과 매우 유사하지만 지금까지 발견 된 최대 길이를 추적합니다 (테이블의 마지막 요소가 최대 값임을 보장하지 않기 때문에).

   3을 반환합니다.

   >>> lcsubstring_length(a, b)
   3
   

   스파 스 테이블 변형은 모든 0을 추적 할 필요가 없습니다.

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

from https://stackoverflow.com/questions/24547641/python-length-of-longest-common-subsequence-of-lists by cc-by-sa and MIT license